I'm partial to the Rega Planar 3/P3 decks. Used ones are a terific value, they're reliable and there's a ton of aftermarket goodies for them. They give you more room to tinker, tweak and upgrade than anything but the Linn LP12. And you get a killer tonearm, too. Haven't heard a Music Hall, but my cousin spins a SL1200. They're good decks, but I prefer Regas in that price range.
For inexpensive cartridges, I like the Grado Black and the Shure MX97E. The Grado is livlier and more fun, but the Shure is great for the price.
I'd go with an inexpensive phono stage at first. One of the $30 ones from Garage-a-Records will work. You can also pick up a vintage receiver at a thrift store, junk shop or garage sale with a phono section and save a lot of money. The receivers have a radio, too, and some of them make good headphone amps, too.
Also, I highly recommend reading the Vinyl Anachronist articles. I can't post the URL from my phone, but Google will bring him right up. Those are good reading and will answer a lot of questions.