Leveling:

I am almost 100% confident that leveling 25 at once will be slower than taking them as 5 man groups. Mobs are tethered. XP gain is decreased in raid. There are a few places in the world where mob spawns may be fast enough for you to lvl 25 via grinding, but no-where near as fast as doing it 5 toons at time.

Class Makup

You have some decent ideas, but as you know about MMO's,there is a lot of information to know about to game, and I don't think you know enough to make a really informed decision. Mages are going to be your easy mode option. They are good at nuking, and their AOE is great, etc. I just don't think you know enough about the game to really understand your decision.

Things you can do.

World PVP is currently not very big in wow. You've cited numbers from warcraftrealms.com but the honest truth is that finding a steady stream of enemy players to kill in the outside world is going to be nigh impossible anywhere other than an enemy city. Upon entering an enemy city, you'll do some damage, but I guarantee it won't take them long to start picking off your characters one by one, despite the best efforts of your healer. Yes, you'll kill a ton of enemies but I don't think the experience will be what you are expecting it to be.

Running Alterac Valley is likely your best option. With 25 toons you'll be a force to be reconned with, killing any single target with ease. However, winning AV with you controlling 25 toons may be difficult due to the nature of the battleground.

Engame PVE is pretty much out of the question though thats been said plenty.

Conclustion:
You might consider rolling on a server that's got an established multi-boxing community. You should almost definately roll a single character or two and play up through lvl 20-30 on the classes you are thinking of so that you can do more than just theorycraft. You should read up on some of the programs people here are using such as keyclone and synergy so that you can maybe improve your setup and streamline the whole ordeal.