What is the best raid/instance for a level 75 Paladin to be joining in order to get optimum PvE gear for dps/leveling with.
Ahn'kahet / Gundrak / Drak Tharon Keep has dropped good gear for me as for my Tank/healer specs. You can try Halls of Lightning in Storm Peaks but best go with very well geared party into Ulduar. So, Storm Peaks is perhaps the best. Nax is the entry level raid instance for new 80's. You could also try and get into a Sartharion raid which you can get to via Theramore on Kalimdor. I didn't really do Naxxramas and skipped it. Went back later for the achievements. Lots of fun in a 25 man raid though.
Basically a good raid party that is well geared can help pull you through the instances.
But looking for the rare gear, you can consider trying to get the Tier 9 gear. This guide is not bad either. A lot of good gear can be acquired via badges. Ultimately you are preparing for level 80 raiding in 10 man dungeons. This guide is a good for an idea about which instances to use for raiding, (it is geared for pallies, but it's good for any class preparing for raids.).
At level 75, you should also have available a set constructed by a Blacksmith which should be fine to level with.
Check out Kaliban's Loot Lists