I liked Morrowind, but I would get lost all the time. (Of course, I was a lot younger when I played it.)
I enjoyed Kingdoms of Amalur for that reason, actually - just checking out the world. Unfortunately the lore of it I found very boring and uninteresting, but it was fun to fight the unique and interesting monsters and traverse the land doing random quests.
Skyrim has a lot of quests without directions so it becomes difficult to continue things you're interested in without using the compass. I did a lot of those radial thief's guild quests and it would be literally impossible to finish them without a map. Part of me also just likes to finish a game and complete everything as I go along - in my "canon" playthrough of ME1, I got all the little resource quests completed, despite knowing it did nothing. I also depleted every planet in ME2 (not to completion, but still...that was a bad idea. >_>)
In Skyrim that's lost a bit because the same blacksmith will ask you to get 5 frost teeth or fire ashes or w/e forever and that feels more fake to me than if I brought him a hammer once and his life was better for the moment.
My dad plays Skyrim all the time (it's the only game he plays) and he loves replaying it as you're talking about, making your own story and such. I think I just enjoy a more narrative approach. Even games like Red Dead Redemption or GTAV I lose interest in after I finish the story.
(Perhaps it makes me less hardcore but in ME, for example, I loved the navigator button. I often used it as a way not to go so I could explore every nook and cranny for lore/items.)
EDIT: I tend to focus on what captured my attention in a game, so whenever I get a quest and get lost, it tends to frustrate me more than say, "oh look new things to do." I often groan when you're doing something in a game like a collection quest or a multi-parter and then the next part is blocked behind a giant "cannot traverse" there blockade.