A lot of good suggestions in this thread, and only a few lousy ones. Well, time for me to throw in my two cents.
First of all, I'd like the return of human enemies that have only one life, like in Morrowind. The first time I killed a few bandits on an island just to return later and find they had returned to life with better weapons and armor, it really took me out of the experience.
I also agree heartily with Limos about the animals. If wolves and bears behaved in real life like they do in Oblivion, we would have wiped them off the face of the Earth 200 years ago.
Like the others who have stated it, I'd like more weapons and armor, or at least rarer higher-level stuff, so I don't get decked out in the best equipment in the game without some serious effort.
Gold being harder to come by would be a plus. In my two or three playings of Morrowind and my one playing of Oblivion, I was wealthy beyond any useful measure really early on. If you're going to give me that much cash, at least let me buy something cool or useful with it. I mean, what do I want with a house? I can play The Sims if I want that sort of thing.
Caves and ruins do feel very generic, and way too common in both Morrowind and Oblivion. I know you want to give the casual players plenty to do, but when I look out in a random direction and know that within a few minutes of traveling, I'm easily going to find some cave or ruin to investigate, I don't feel like an intrepid adventurer, I feel like I'm being handed things to explore.
And finally, to weigh in on the fast travel debate. Personally, I'm not a fan of Oblivion's ridiculously easy travel scheme. Yes, many people just want to be there and get the job done, and I can respect that. But when you can zip anywhere you want, you sacrifice a lot of the immersion you might experience otherwise. Yes, you don't have to use it, but I don't think a game should make you think "I'd like to get there traveling overland, but I have to be up at 8:00 tomorrow for work, I'd might as well just be there instantly."
I actually thought the travel system in Morrowind was pretty perfect. Between silt striders, mage's guild teleportation, boats, Mark/Recall, Divine/Almsivi Intervention, and the Boots of Blinding Speed, I never found it very difficult to get around. Replace the Boots with horses and you have a perfect system that also seems realistic.
I also toyed around with having the fast travel system have the character set out toward the goal, following what roads took you there. The screen could black out and then come back if you were attacked on the way, arrived at your destination, or weren't able to reach it because it was off of a road, making the rest of the journey necessary to physically travel yourself. I think this might be a decent compromise.
Oh, almost forgot - of course the leveling system in Oblivion was ridiculous, and needs major work. I want to be heavily outclassed by some enemies and take down others with ease. Maybe have different colors/physical appearances for what level a certain type enemy is.