IMO, both Billy and Red Haired are more for Intermediate at least. Billy IS a good tune to learn to play on the low strings
Red Haired Boy can be tough if you have trouble with the hornpipe rhythm. I can do long/short (hornpipe) but I can't do short/long (scotch snap)

Beginner:
Old Joe Clark
Cripple Creek
Boil/Bile Them Cabbage Down
Cluck Old Hen
Golden Slippers without ornaments
Angeline the Baker
Swallowtail Jig, no ornaments
Amazing Grace
Star of the County Down
When Johnny Comes Marching Home
Darling Nelly Gray

Intermediate:
Gal I Left Behind/Brighton Camp
Soldiers Joy
Arkansas Traveller
Harvest Home
Road to Lisdoonvarna with some ornaments
Chinese Breakdown
Over the Waterfall
Westphalia Waltz
Rakes of Mallow, or this could be Beginner
Jesse James

Now, my comments on Cruisers' List:
NOTE! This is just MY opinions on his suggestions!!!


Cripple Creek--OK, see above
Old Joe Clark--OK, see above
Red River Valley-Good Beginner
Filimiooriay--don't know it, no opinion
Rig A Jig Jig-Same
Flop-Eared Mule--Intermediate, the schottische rhythm can be diff.
Old Rosin, The Beau--I'd say Intermediate because of the 'snap'
Crossing Over To Ireland--don't know it
Home on the Range-Easy
Black-Eyed Susie--don't know it, at least under this title
Crawdad--Fairly easy
Bowling Green--don't know it
Cumberland Gap--Easy, good vocal for beginners
Fly Around My Blue-Eyed Girl--OK, but just keep it slow
More Pretty Girls Than One--don't know it
Ground Hog--I see this as more Talkin Blues, not a lot of melody
My Home's Across The Somky Mountains--don't know it
Sail Away, Ladies--Intermediate
Sally Ann--Depends on which one!! (smile)
Red Apple Juice-OK, as are most of the modal tunes
Sally Goodin--This one is VERY diff for ME...just can't get it
Sourwood Mountain--OK
The Wabash Cannonball--Easy, good for learning double stops
Salty Dog--Easy
Nine Hundred Miles--Is this same as 500 Miles? That is easy
Arkansas Traveler--Just watch the speed and ornaments
The Gal I Left Behind Me--see my list
Mountain Dew--Good for double stops, also, Do Lord
The Irish Washerwoman--Intermediate, also watch the speed
Garryowen--rhythm is a bugger all, IMO
Turkey In the Straw (ol' Zip Coon)--Watch the speed. Good for double   
    stops, wants to be fast
Ragtime Annie--The rag rhythm can be diff, B part is fairly easy

So many tunes, so little time. Another very good book is the Fiddlers Fake Book by David Brody. Gives optional ornaments, several settings, discography and it used to come with an optional CD, I think.

Not intending to offend anyone, but we all have different opinions on what is 'easy' or 'common/popular'. Cruiser is correct that location and style are big considerations.