I would go for the pseudo-3d approach and visualize the height with a vertical offset. To avoid the problem that parts of the map are concealed by cliffs, I would only use a few pixels per height level and avoid having differences of more than 4 or 5 levels.

As you can see from this mockup, this is good for visualizing that the tile to the north is higher than the tile to the south, but not so good for visualizing that a tile to the south is higher. For that reason I would recommend to avoid this situation in map design... or you give the player the ability to rotate the map so that they can always choose the best angle to visualize the situation. But don't rely totoo much on this - you want the player to fight the enemy, not the camera.
