Uh, guys? In what world is dodging AoOs overpowered? Everyone already has five-foot steps. It's not hard to get 10' on those "five-foot" steps, too, with magic items. And that's ignoring free movement like Anklets of Translocation. Tumble is hardly an impressive improvement.
On the subject of DC, it's not really bad when you keep perspective. (I was going to link to a relatively well-known page pointing out that people are really level four or five at the max, but I can't link.)
Finally, you're forgetting how easy it can be to manipulate movement. I mean, even a knight can pretty much shut down tumbling, and, well, it's the Knight. And if you really, really need to kill something that's moving, just ready an action.
I like the idea of adding the opponent's BAB to the base DC of 15. It will work both ways though and the monsters will have to abide by it as well.
I'm sorry, but that's a terrible idea. Look at animals, just for example. They're hardly the most skilled or trained fighters, but RHD gives them comparatively large BAB.
This gets even worse as we get to higher level, because many monsters have massively inflated hit dice just to be even remotely threatening. So, basically, you're putting arbitrary restrictions on a simple skill that's largely unnecessary. It's punishing people who don't want to fork over 1400gp, and can be easily avoided.
Even at low levels, when you might only have a 50-50 chance to avoid being hit, it's a low-cost method to avoid damage a good amount of the time!
And that's a problem? Are you saying that rocket tag is great game design?
Wizards have enough skill points that a couple every other level is a good investment.
No, no it really isn't. UMD, Spellcraft, Concentration, Knowledges, and prereqs are all much, much better investments than something you really shouldn't need, especially on a wizard, who really should never get hit if they're being competent.
I like the idea of adding the opponent's BAB to the base DC of 15. It will work both ways though and the monsters will have to abide by it as well.
It's a terrible idea, as outlined above, and what monsters will actually care?
The way we decided if Tumble in those 3.5 days was too easy was not by what the PCs could do. It was decided to be too easy when enemies tumbled past the front line of Fighters and attacked and nearly killed the poor Wizard in a round.
How? No, seriously, how? Miss chances, simple, long duration buffs, there's little reason a wizard should get hit, even in core.
Also, what was the wizard doing so close to the enemies if he was that fragile?
They thought it was too easy for bad guys to move around and attack weaker party members while ignoring the more powerful combat focused characters.
And then what's stopping them from just eating an AoO or five-footing it? It's not like most monsters don't have HP to burn, and there's no downside unless they're already low on health. If they're intelligent creatures, why not use magic items? Or, in other words, protecting people doesn't really work in 3.5, news at 11.