Glad you went ahead and posted it. I was where you were at one time, and it took me posting, doing weekly challenges, and reading lots of other people's topics before I got the hang of everything I needed. The weekly challenges were the most helpful for me though, in terms of execution -- it made me pull my head out of my own work to see it the way others would see it, not to mention the 'challenge' part teaching me how to manage colors.
Speaking of managing colors, Square did this really well -- the reason the sprites are near-unreadable when you zoom in close is because they pack a lot of detail in a small space with those colors. The reason they read well is because Square put in a lot of trust to the CRT televisions that these games would be played on. The CRT's would blur the pixels together and you'd essentially be 'painting' with light because the CRT's would naturally blend them and make them look more organic, so you never really saw what the squares themselves looked like -- you'd just be 'painting' a picture!
Nowadays this is rarely the case because everything is so HD that a blurry pixel is considered a negative thing. Even in pixel art for games on the PC, it's rare to find this kind of 'detail' packed into a single sprite because it tends to look muddy or jaggy unless zoomed way out to where you can barely see the pixels (OR you can use a nice CRT filter possibly?
)
Anyway, C+C:
Your characters don't look bad at all form-wise. You've pretty much got the look. The guy leaning against the wall is a nice touch too! The only real issue is your color choices -- you need some sense of hue-shifting (i.e. shifting toward the color of the light source for highlights and shifting toward the color of shadows for the shadows)
The biggest and most glaring issue with this besides the lack of detail or direction in the environment (relative to the size of the screen!) is the washed out colors and the abundant over-use of dithering!
Tiles can be tricky in general (due to their modularity) and tend to be the bane of my existence in regards to pixel art, but they follow *most* of the same rules that characters do -- with some exceptions:
Firstly, the perspective is orthographic (that is, depth is not really depth but height, depending on the overhead angle you choose), whereas characters can just about be at any angle and the viewer won't care.
Second, the characters MUST stand out, so tileset colors and details should *never* overpower the characters. Therefore you had the right idea to keep the BG somewhat desaturated, but at a certain point, "desaturation" == "uninteresting", so it is a constant balancing act between characters and their BG tiles!
Finally, you NEVER want stray (single) pixels in a BG tile because it draws the viewer's attention (think of how people are naturally able to see faces in ordinary things such as an electrical outlet or a car's grill and headlights) -- a stray pixel is like "hey, there might be a face over here!" and your eye is drawn to it -- and this is why extensive dithering is a no-no, /especially/ on repeating tiles. It's distraction city.
In regards to THESE specific tiles, you might want to make some kind of portholes to the outside world on the train (most trains have windows to prevent claustrophobia in its passengers) and perhaps some other bits and bobs laying about.
You'll want to also use some blues in the gray walls and purples in the red floors to show that there's some semblance of night outside (assuming you put windows in, or if there's ambient light bouncing around ANYWHERE in the train).
Finally, you'll want to establish a light source. It's clear you've got a Chrono Trigger 'inspiration' there, but even this game had a variety of shades to indicate the light on the floor and walls. Go look at one of the maps of Crono's room both before and after opening the window in his room. That should give you a hint of how to light an area with tiles.
Also, one final note about 16bit tiles -- even though many games appeared to use them as 16x16 squares, most tiles were actually 8x8 and worked into one another to help define things like shadows, borders, rims of objects, and other smaller bits and bobs hiding in the shadows. You should see the Star Ocean "commercial critique" thread here on the forums to see some of the tilesets they used in that. It should give you an idea of how these sorts of tilesets are setup.
Hopefully this helps! Good luck -- and great taste in games dude!