might want to hold your horses and wait for the recently announced EFS 18-200 f/3.5-5.6IS. it's likely to be in the $1000 range though, but will perform all the functions (wide, tele) reasonably well.
A superzoom (10x or better zoom range) is a decent alternative if you don't want to carry around too many lenses (holiday, street, etc), but there are compromises in the image quality.
sigma 18-200, tamron 18-250 and 18-270 are all viable 3rd-party alternatives in the $800 range (IIRC), but you can get them cheaper used.
i started with a superzoom myself to help me find out which are my favourite ranges.