hey,
1) ship: i explored in an Adder with an intermediate discovery scanner to finance my first AspE. fine ship for doing it. if you don't have horizons, and therefore can't land, a hauler is a very nice starting exploration ship, too.
2) destinations. i recommend the eskimo nebla as the visually most stunning planetary nebula <1000 ly from the bubble. i recently visited the spirograph nebula, which is also great. betelgeuze is another destination close by, especially if you have horizons, because it has a landable very close to that giant! alternatively you could check out the ancient ruins - there are over 60 by now, or the alliance research bases in the california nebula with their fungal growth .... all around 850 ly from the bubble or closer.
if you want to go really deepspace, i'll second zieman - eta carina star and nebula, the supergiant x carinae and the statue of liberty nebula make great medium range destinations - and that general direction isn't explored as much as the straight line to sag a*, soll you'll get a lot of first discoveries. but generally i'd recommend doing a <1000 ly trip first, as exploring isn't for everyone, and you should check out whether you like it at all.