I think it has to be sufficiently different to be (truly) interesting. Almost all of the antipaladin/paladin/monk/ranger/archer stuff can be handled by MDoA... so what's the point in cobbling together a new and separate class with that name? As Ravenheart87 said, specialist wizards are also included.
1. A gnome class might be interesting, but I'd want the gnome to be not just a "specialist" wizard with some MDoA-like spell power. See, for example, this: http://en.wikipedia.org/wiki/Gnome
Maybe have a gnome class much more like a svirfneblin from AD&D? (Except not absurdly powerful.) The ability to speak/communicate with normal animals and elementals, or heck, the ability to just speak with everything without penalty, might be kinda cool. And maybe instead of being magical, they're anti-magical. Could be sort of like a magic-sink, like a party's defense against a magical effect (much like a halfling is a good luck charm, a gnome could be a lightning rod, literally).
2. A half-orc class could be interesting too. I'd probably take dwarves as a model, so a HD that was slightly less than a warrior (d12 probably), they still get MDoA, and I'd probably give them a bonus to use a two-handed weapon over a shield, so maybe give them a regular d20 for initiative when using a two handed melee weapon. I also like the idea of them being able to track (and possibly fight in the dark) by scent, so maybe give them a light sensitivity but a bonus underground in standard (dim) torchlight. And maybe, maybe, a set of pre-level-1 occupations involving mechanics, siege engines, making chariots, taming wild animals, or something.
Also, and I know I'm probably the only one, but I really don't like the rage mechanic that was proposed earlier. In my opinion, something like that properly belongs in the role playing side of things, not the system mechanics side. I think it'll just end up being cheesy and overpowered. Instead of that, maybe just make them heal up twice as fast as normal characters (which would be helpful as there aren't any clerics among the orc tribes).