I had been considering an idea similar to Subanark's, only have the altars appear, but be unususable to make it clear there were things to unlock.
I was thinking that, in order to assist learning, have only unlocked altars appear in the central normal dungeons (as happens now: If you've only got Tarog, he always appears), and only unlocked altars and the altars associated with that direction appear in directional normal dungeons (So you sometimes see Glowing Guardian and Dracul in the east, even before you unlock them, but they won't help you).
But once you got to hard+ dungeons, all altars would appear, and the risk of facing locked altars would become a factor.
In order to assist people who are unfamiliar with them, meditating on a locked altar would give a hint as to where to search for it. (eg: "The markings on this altar are similar to some found in dungeons to the east of your kingdom.")
This would allow strategic altar unlocking in Den of Danger, etc, but those dungeons have so many viable strategies that it would be pretty unimportant.