Bomarc's comments are very relevant. I'd go beyond his remarks to add that the phono stage can make a huge difference, since it must take a very weak current generated by the cartridge and amplify it in a very linear fashion before passing the signal to the preamp. Whenever an audio component is responsible for handling very low voltage signals, the designer is faced with a real challenge. Fortunately, as others have noted, there are some very good, moderately priced (by high end standards) phono preamps on the market today, such as those made by Creek, Lehmann Audio (Black Cube and Black Cube SE), Coph Nia, etc.
If you plan to get a better quality cartridge (in the $500-750 range), then you should probably be thinking of a phono preamp that costs about the same.
As a personal recommendation, I urge you to consider the Lehmann Audio Black Cube SE. About two years ago, I looked at a number of phono preamps for my system, and thought the Black Cube offered a lot of performance for the price, particularly when purchased used on Audiogon. I bought the Black Cube, and subsequently upgraded it to the SE version, which provides significant improvement over the standard version. As a caveat, however, there are some users who think that the Black Cube SE is a better phono stage when used with moving magnet or moving iron (Grados, specifically) than when used with moving coil cartridges.