Of the 3 currently available US PS2 DDR games (Max, Max2, and Extreme), I'd have to vote for Max2. It's the most newbie-friendly with the best music and interface. Extreme and MAX follow in that order. Extreme 2 is due out at the end of the month, and it looks to have a lot of great songs included.
On the other dancing games front, I'd recommend at least taking a look at In the Groove. It's put out by RoXor/RedOctane (and currently on sale at RedOctane.com for $19.99). The songs are longer (2:00 rather than 1:30) and the stepcharts are a lot more interesting. It is more difficult than DDR, however. Pump it Up just also released a home version of PIU:Exceed with mat (5 arrows, not 4), but at $59.99 for the bundle I'd recommend waiting for a price drop (I expect it to be about $20 within a year's time)
As for other rhythm games, Taiko Drun Master just had a big price drop at BestBuy, you can get it for $20 (controller included)now. It's the game Donkey Konga as ripped from, and is a good bit of fun for the price.
But yes, you could always download Stepmania and the Bumper packs of songs, but it's just missing something for me.