My first turntable was a piece of JVC plastic during the early 80s, although that was back when plastic bodied TTs weren't as bad as they are now. Not knowing much back then, I bought an Ortofon MC cart as my amplifier had an MC input, and it sounded great compared to the cart that was on it, despite the cart being two thirds the cost of the deck.
When putting a better quality cartridge on a cheap deck, you will still hear certain benefits of that better cartridge - it's just that its full potential and certain benefits won't quite be realised. How much of the cart's potential that can be realised really depends on how good the deck is - and when I say how good the deck is, I don't mean how good it looks - it's how well engineered it is. Something like An Audio Technics AT-LP5 is a good budget deck that can handle a good cart.