Thanks for the feedback, guys.
As far as the palette goes, I don't really want to change it since the CGA colors is what I associate with games back then. I was mainly wondering what I could do with the same palette.
I think you should break up the straight lines on the waterfalls, the straight edges are killing them.
Yeah, I was hoping the sparkly effect would hide the straightness a bit.
But perhaps the text should be placed over some sort of background?
Maybe blacken the inside of the big monster's mouth, that would give it a bit more depth.
Also, have you considered using dark red for the stalagmites/tites? I think that could possibly push them into the background a bit more. Right now there's just a lot of blue going on.
I tried the red for the cave background, but the dark blue is currently the darkest color in the palette, so anything brighter adds to the contrast, making it busier. The contrast in hue between the foreground and background was also a bit too harsh. I don't really mind the blue. It makes the cave seem cold and it also serves as a nice background for the text since the yellow really pops out against the blue.
If this underground world has relics in it, suggesting a lost civilisation, then it would be cool to have squares of cut stone, and leftover bits of wooden structures to also 'break up' the rock tiles. Maybe carved faces, also?
I think the cyan outline looks fine, but if it isn't subtle enough, how hard would it be to make it fade in and out like a soft glow (stepping through darker colours, rather than an alpha, I assume)?
I've been staring at the reflection animation for your crystals with unblinking appreciation - it's amazing! And is that a little page to fit into the diary - does it have game hints and story-advancing clues? I wouldn't be able to wait to collect them, even over treasure!
Are you still going to have coins? I think a stamped image in the center like an eagle or a fish would help them look flat (especially if they had a raised edge).
Is this going to be a mockup, or a working game? (looks pretty convincing atm!)
I like the idea of the alternate layer you showed in this post, which really gave a suggestion of depth and intricacy.
I'll try to come up with some carved, ornamental tiles. I won't keep the coins, since there's no need for currency in the game (i.e. no shops). I also decided to go with a neolithic culture, which rules out metalworking. I can try to add another layer to the background, but with statues or something like that, but I've so far found it difficult to make an additional layer subtle enough with the current palette.
As far as diary pages goes, I was thinking I'd try to combine the story with a tutorial. The pages will describe the discoveries of an anthropologist lost in the caves, but they'll be found out of order so that the items are explained before you find them. The pages that only contain information related to the story will be scattered a bit more, so I guess it would be a little quest in itself to find them all and combine them.
I don't know if it'll actually turn into a game at some point, though. I need to figure out more of the gameplay before I start thinking about actually making something out of it. I also want to give the ecology of the game a bit more thought to make it seem both consistent and sufficiently varied. I'll keep the current monsters, but I think I might need to make them a little bigger.
I like the glow suggestion, so I'll experiment with some kind of glow or sparkle effect. Maybe I'll do something similar to the reflections in the crystals for the other items as well. As a digression, making that animation was a straightforward procedure, so I thought I'd explain how I went about it.

1) First I colored in all of a crystal's planes with each color indicating a similarly angled plane.
2) Then I decided which direction the light would move in (horizontally, in this case). I indicated the planes I'd use for the animation with white and light green going from one side to the other.
3) I made a palette swapped version of the crystal so that the colors were roughly halfway between the original and pure white.
4) I used the image from step 2 as a mask to isolate the brighter planes while leaving the white from step 3.
5) Then I put the resulting brighter and white parts on top of the original crystal.
After that, I tweaked the individual frames a little so that the edges wouldn't be too sharp and to make sure the animation would be smooth.

Here's an attempt to soften the edges of the waterfalls, and also text with a background. The page looks a little crude right now, so I'll try to polish it a bit more and experiment with the colors. It does block more of the player's view this way. I'd rather not freeze the game while the text is displayed since I've always found that jarring, but now it's a bit more obvious where the text is coming from at least.