Fisrt I want to say, I love the random map. The more randomness, the happier I am generally.

However, I think it'd be a good idea to also have a less-random dungeon wich always generates within sight (or nearly so) from the starting location. As it stands now, I sometimes have to eat all my food and see my character starve before even finding a location to enter. While there's usually something to eat inside, if I'd ever survive that dungeon (never happened so far :p) it'd be a real problem to get back to town.

The solution at this moment is to take the survival skill, but with more skills implemented, that will get far more painful. It will also get very much more dangerous, looking for that first dungeon, once there are wilderness encounters. So just one little location to go to quickly and relatively safely and get some xp, gold and items would be a great help to get a character started.

You could do it just for testing and remove it again later.