Roger and others advice is spot on Shaun
for an instrument for that will keep you going for many years its easily an 8 or 10" dob the 8" is very portable.
while I found my old 80mm refractor great for lunar viewing and planets
it really had little use for deep sky observing.
one of these little finders in addition to what comes with the scope (they don't cost a lot)
http://www.youtube.com/watch?v=NH33pXGkNF8
and some simple star maps available free around the web
and you'll be busy for years.