As you mentioned map_features already I'm not sure if you have realised yet or not that the yellow lines in map_features.tga represent cliffs ?? You can add more cliffs to map by adding 1 pixel line using the same yellow colour - dodgy bit is trying to get your cliff to line up with your coast.

To do that re-size a COPY of your map_heights.tga down to map_features.tga size, copy that re-sized version into map_features as a new layer, select all the sea area in that layer then with selection still active switch so you are only viewing the original map_features.tga, invert the selection and you should be able to paint your cliff in the right place. (note that works a lot better if you have PhotoShop and can use 'nearest neighbour' re-sizing, some other programs re-size mechanism don't tie up as well with the way the game relates the various maps).

Once a cliff is placed you and AI can't land troops in those locations.

There is a cliffs_debug.tga that gets generated when map.rwm is re-generated (that is found in Rome - Total War upper level folder) I assume that is meant to correct things if you place cliff in sea - but have never really figured out what you're meant to be able to do with it.....