For what it's worth, I just ran from Leyawiin to Bravil in about 11 minutes. My character has 121 Athletics, 158 Speed, and 79 Acrobatics and I was just doing a normal run (heading to Bravil to return an item for a quest). I avoided a bunch of combat and split my time between the road and some cuts through the wild. I did end up fighting (in total) 3 bandits and a bear in three separate skirmishes though, as it's difficult to avoid all combat (well, I am fast enough to run away from anything, but that'd be boring).
I'd say the map is a decent size...large enough for me to view a run even from Skingrad to Bruma or Anvil to the Imperial City as a bit of a task (and there are many larger distances than those). Yeah, you might be able to run across the map in a relatively short time if you tried, but there's a lot of depth and the size is evident if you just sit down to have some fun. Plus, there are all the "invisible" distances. On the world map you don't see the expanses of the interiors of the land...all the forts, caves, cities and their structures, sewers, etc. I'm 125 hours or so into the game and I still haven't explored the whole map because I let things develop "organically" and generally don't purposefully target things for completion. Just today I had some time to burn until my window of opportunity opened for the quest I was doing so I trekked up the eastern border of the map a bit and discovered some camps. forts, and caves that I had never seen before (not to mention tons of Nirnroot

).
Oh, also, the saturation of "stuff" in the land I think is rather good...despite the map's size you don't do much running through boring emptiness. I remember playing Just Cause on XBox...it has a massive map, the biggest I've seen in a game...but there's nothing to see in most of it. I love wilderness, but it did get boring. Now, Oblivion's wilderness-filler gets repetitive too, but there is a lot to it as well...forts, ruins, camps, settlements, inns, caves, Oblivion gates, interesting things to see—and of course there are always creatures to kill and plants to harvest (plus, the world is just beautiful).