Regarding realms, I can only recommend Icecrown. It's x3 server, but beyond that it's oddly enough closest to blizzlike. Frostmourne is x3 seasonal progression realm with slightly tuned encounters (instances, raids) to make them a bit harder. Lordaeron is x1 realm with higher tuned up instances and raids. Neither these are that beginner friendly.
Icecrown might have some long queues during peak times, so maybe Frostmourne would be the second choice.
Races have very little impact on balance. That's something you could consider at end-game min-maxing. Go for the looks and aesthetics I say.
If you divide classes crudely to armor types and roles, I'd say plate melee DPS are the easiest (only considering leveling, not instances or raids) to learn and play.
Randomly throwing easy classes?
Hunters, they get pets at level 10 and pets can be very useful. Just remember to feed and heal them.
Warlock is the spell casting hunter counterpart. You'll have a pet and it can be useful. Instead of your typical x/bow, you use spells.
Druids are versatile. You could be a cat DPS, bear tank, or owlkin casting damaging spells. Even a tree eventually, if you want to heal. Might be bit overwhelming for new player with its choices, but worth it.
Warriors. Steady damage, some survival tools.
Paladins, like warriors, but with spells. Healing spells especially. Very beginner friendly as you can heal yourself.
Shaman could also be fun, haven't leveled one in ages. Should be relatively easy.
Frostmourne is basically just icecrown but seasonal (and a little harder) and eventually they get merged into Icecrown so if you play on Frostmourne then you will probably end up playing on Icecrown eventually.
Icecrown has queue so if you never donate the minimum amount then that might be bothersome.
Icecrown and Lordaeron face each others in arena and bgs. On Lordaeron it is not possible to buy items for real money and raids are harder so it is a lot harder to get BiS gear on Lordaeron (this is pretty negative when you have to fight people that bought full BiS gear or got it from easier raids which are easier both because of difficulty and overgearing on icecrown).
There is more new players on Icecrown, since it is much faster to level there, which means that even though there is more BiS geared players than on Lordaeron there is more players with worse gear. Because of this I would guess that the average ilvl in WG is probably around the same.
For the most part I would say Icecrown or Frostmourne would most likely be best but if you can't ever donate the minimum amount (which allows you to skip queue and also use the trade section where you can sell gold and characters for coins that you can use to buy BiS gear without having to donate more money) then it might not be very good when you get into several hours of queue, so in that cause Lordaeron might be better.
if you want to have a good starting experience, go Frostmourne, progressive realm will let you get your gear slowly and roughly in line with the rest of the players
if you want to cough up the moolah for gearing your character to near bis(best in slot) before you're allowed in any raid (thanks to unrealistic expectations for minimal gear requirements for raiding... basically twice overgeared) go Icecrown
if you want a true trial by fire, where it's get good or go home... try Lordaeron, because of the raid difficulty the requirements for raids do seem high, but it's quickly obvious why... Lordaeron also seems to have more of a community once(if) you get into big guilds