There is a very slight (+/-3 points) stat difference based on race; starting stats are determined mainly by your race. Your race choice determines your faction allegiance (either Horde or Alliance), your starting area, and your Racial Traits. What you can do with your character, however, is determined mostly by your choice of class. See the Race and Class pages for discussions of the different race and class options.
As your character increases in level, these racial differences become negligible with the exception of racial traits, which can be strategically useful in some situations. Therefore, play the race that you find most interesting based upon appearance and racial traits, and don't sweat the little differences.
Character creation screens circa Wrath of the Lich King and Cataclysm
One important note: The Alliance vs. Horde distinction is a very important one, as you will only have very limited interaction with those on the opposing side, outside of combat. If you're playing on a server with friends, you all want to be on the same side so that you can chat, etc., so make sure you all either select Horde races or Alliance races.
Can't decide what class to play? Make one of each that sound interesting (you can have up to 10 characters per server), play them up to level 5-15 or so, and decide then. It only takes an hour or two to get the first few levels, and then you'll have a much better idea of what it's like to play each class. You may still miss out on the more significant parts of playing a class, as some important skills are given at level 20 or 30 for the first time, but you will get the gist of the class so that you can at least understand what higher level characters are talking about. Alternatively you can read the description of each class to have a general idea of them.
An important factor to consider when choosing a class is whether there is going to be much demand for characters of your class in groups. Generally, tanks and healers are in higher demand than damage dealers for most servers. Therefore, if joining instance group/raid is you first priority, choosing classes that can spec tank or healer may improve you chance of getting invited.
For those who want to be the tank in instances, warrior (Protection), Death Knight (Blood), paladin (Protection) and druid (Feral) are your choices. With the right gear and spec, they can have higher health and armor than the rest of the party. You can absorb large amounts of damage and prevent others from being attacked. Warriors and paladins can wear mail at lower level and plate after level 40, which provide them with very good armor and survivability. Druids can only wear leather or cloth. However, they get Bear Form and Dire Bear Form at level 10 and 40 respectively, which gives them large amounts of health and armor bonus (Bear Form is similar to a Warrior in Mail armor, Dire Bear form is similar to a Warrior in Plate armor).
If you want to heal others, priest (Holy/Discipline), druid (Restoration), paladin (Holy) or shaman (Restoration) can be considered. All of these classes, with specific talent point allocations, will make a competent main healer. In addition, all of them provide useful buffs to the other members of the party. Paladins have auras which buff all players in their group within a radius, and beyond that have blessings that they can cast on anyone that give different benefits. Shamans have totems which act similar to auras in that they buff party members near them, but they have very different benefits. Druids can increase the critical hit chance, spell critical chance, or amount of healing done to the entire party, in bear/cat form, or moonkin form, respectively. Priests' stamina buff is always useful to everyone. With certain specs they can also help party members regaining mana at a much faster rate.
The five classes mentioned above can also be damage dealers(DPS Damage Per Second) with the right gear and spec. However, there are four classes that can be considered as pure damage dealers: mage, warlock, rogue, and hunter. Mages excel at dealing massive magical damage to their enemy. Their powerful AoE damage is helpful in many encounters. Warlocks have abilities to summon a demon as a pet which will do the player's bidding, and are 100% controlable in every aspect by the summoner. They are famous for their DoT spells. Rogues have stealth abilities, can open locks, and can deal lots of damage by sneaking up behind enemies and using stealth only abilities such as Ambush. Hunter is the only ranged class in game that do mainly physical damage. They can tame pets to help them in a fight. Depending on what type of pet you decide to tame, you get different spec options for your pet. Go to the Pet talents page for more information on pet specs. Hunters also have the unique ability of putting down various traps to help the party and handicap their opponent(s). Depending on their spec, they can also boost their party members' damage output in different ways.
To see what the population for each class is on a given server (or all servers) for one faction or another, see Warcraft Realms.
Picking a name can be tricky. Nearly everyone wants something unique, awe-inspiring and/or "cool". However, the name you pick does tell others something about you.
Keep in mind that your name needs to be easily typable in conversations, and that it probably shouldn't clash too much with the warcraft/medieval themed environment. Names that you probably shouldn't pick include:
Legolas - Wrong universe. Too unoriginal. Far too commonly used already than you may expect.
Mrcoolguy / Iownyousohard - More than anything, this suggests to other people that you're immature. Maybe you are, but not making it quite so obvious makes it a tad easier to earn the respect of other players.
Agsdjasgd - People will assume that you don't take the game seriously and/or that you're a farmer or ninja. Neither is good for you.
Lukeskywalker - Wrong time, wrong universe.
Onyxia / Illidan / Arthas - No, you are not these lore characters. Picking names like these is a sure-fire way of having a GM enforce a name change on your character.
Joë / Jôe / Jœ - If you use special characters in your name, expect to find that most people do not know how to type your name (which means a lot of trouble later in the game), and you may encounter error on your armory page as well as when you try to link to it. See below.
On RP and RP-PvP realms there are additional naming policies active. They can be found at the official Naming Policy page (EU, US) under the title "Only applied on Roleplaying Servers" and at the official Roleplaying Realms Policy page (EU, US).
Picking something unobtrusive that actually sounds like a name is usually your best bet. Your name doesn't have to be cool to make you cool. You make your name cool by who you are and what you do; WoW may be massively multi-player, but the core population of any given server is really only a couple hundred players. Rumors, names and stories of feats do travel quickly.
What if the name you want is already taken? It is commonplace to see several spelling variations on a name, but you should stay away from strange characters (like æ, ø, and œ) that are not common to the language or are in the extended character sets. The biggest reason for this is making it easier for others to type in your name. So, if you find 'Joe' is taken, don't replace it with 'Joë' or 'Jôe' or 'Jœ'. Instead, try 'Joey', 'Joseph', or other variations.
Lastly, you can choose your gender, male or female (of course!) when creating a new character. Functionally, there is no difference between a male or female character in effect, only appearance. The only in game differences are the appearance, animation and speech. When in doubt, choose according to your real gender. Nevertheless, some people like to do otherwise for various reasons. As a rule of thumb of playing WoW as well as any other MMORPG, do not assume the gender of anyone by the look of their character!