Quick edit: Lowering contrast on the floor makes the other things more distinct even without outlines.
Also, I added shadows for the stools and the suggestion of shadows where the back walls touch the side walls.

Maybe try using a similar perspective inside to the one you're using on the outside view of the building, so two sides of things are visible, rather than only one.

For example:

These are really cute - I like them a lot!

The only thing I'd suggest is to try a slightly less spherical head.
Here's a quick edit I tried:

Remembering I'm a newbie here when you mentioned the contrast of the red mars tile did you mean the colour ramp had colours where the luminous values (my colours were picked by contrasting the luminous value) were too far apart or something else?

I changed the colours for the mars tile and also added a black background with stars, though they look too clustered it's just a simple mockup to see how well all the colours work together.

That's a definite improvement. But there are too many gaps between the rocks - make the rocks larger and the space between them smaller; make them touch and overlap - and think of them in 3D! (My edit isn't great either)

Hue shifting is fun - try it! (Search the forum for plenty on this topic - and see what I did with the ground colours)

It looks like you've anti-aliased the monster against a lighter coloured background - there are messy pixels around the outside.
Also, I would suggest you should leave doing most AA till last, since it makes editing harder.

And finally, the shading on the monster is somewhat off - the shadow and highlight suggest different light sources to each other. Maybe try reading: http://www.itchstudios.com/psg/art_tut.htm#light_stuff.

The PS1 of course can do 8 bit textures (dunno about 24bit, but I doubt it), but the main problem of the ps1 (ps2 as well in fact) are their shit video ram amount.
The PS1 has 1 megabyte.

It can do 16 bit textures, but not 24.
16bit was normally only used for a few effects where the last frame's image was used as a texture (I think quite a few JRPG battle transitions used this.)

The other thing to note about the 1MB memory limit is that this has to include the surface you are rendering to (normally two of them for double buffering.)
So with a render target of 320x240 (16bit), your double-buffered screen takes 300KB, which is nearly a third of your VRAM used before you've got a single texture!
And of course it gets even worse if you want to run in higher resolutions.