I started digital photography with a Nikon D3100 - great camera and reasonably inexpensive - leaving more money for lenses (although I found the 18-55 kit lens perfectly acceptable). An 18-200 is a great lens for travelling though as it would cover most situations you'd want to shoot and means you wouldn't need to change lenses. I have also used my sister's Canon EOS 550D and it was great.

Find a camera shop that will let you try out different models (Nikon, Canon, Pentax, Sony, etc.) so you can find out which is best for you to hold (important if you're taking it on holiday and will be using it frequently) and use. Prosumer cameras like the D300 can be heavy to lug around all day. I haven't held the D7000 so wouldn't know.

Don't get hung up on or seduced by megapixels.

All in all, I would echo Razormac's comments and check out entry level models from Nikon or Canon.