One of those Crosley models with the built-in speakers and low-maintenance hardware isn't an *awful* recommendation, especially not for a first-timer. That being said, they're pretty bad. But only if you know how to judge quality properly, which someone who just bought their first record probably doesn't (and shouldn't).
I'd recommend a Crosley model that fits a pretty low budget. Give it a shot and work on building your collection. Too many people try to start off with serious hardware and then just end up with a bunch of sunk cost. If you get into it for real, you'll be able to unload the low-quality player easily and spend real money on something new.
BUUUUUT... if you wanna skip the novice step and go straight to something intermediate, the AT-LP60/120 recommendations in this thread are spot on.
Edit - For some background, I started off with a hand-me-down (read: free) Crosley all-in-one thingy. I stopped collecting after 3 months and was relieved to have not invested too much on the hobby. About a year later, I picked it up again and bought a solid set-up for myself within 6 months of re-starting. It worked out well for me :)
Well...at least here's one person who hasn't torn apart my suggestion...