High Elf mage would be fine. You will start at Felewithe. Your newbie area will be Greater Faydark. You should be able to find groups at the Orc Hill, and then move into Crushbone. My recommendation is getting to at least level 4. Make sure you get your pet. Then make your way to the orc hill where you should find a group.
Here is a resource to help you navigate the zones:
http://www.steveprutz.com/eq/
You can hang out at orc hill for a few levels then move into Crushbone. Both those areas should be vibrant and busy with players. The Felewithe starting area probably will be a bit empty, but with a bit of travel you will find the people.
Also if you find me doing a newbie night I would be happy to come guide you to those destinations!