1. Is there such a thing a good all-purpose lens? Travelling around it would be nice to minimize lens changing but still be able to take good pics. Is a 18-135 or 18-200 going to do that? Or better to go for an actual telephoto lens?
No. There isn't. The 18-200mm lenses are versatile w.r.t. zoom. The image quality is somewhat lower than the kit, but is probably good enough for beginner use (others will argue with me about this).
The key issue is with maximum aperture. The superzooms and kit lenses are all f/3.5-5.6 or f/3.5-6.3 or similar, which doesn't do well in low light, and doesn't do well for limited DOF. Personally, I prefer an 17-50mm f/2.8 zoom to my 18-200mm for almost all purposes, and most of the time, I use a fast prime like my f/1.7 50mm.
2. With Canon is it necessary to look only for USM lenses or will the others work fine for a novice?
3. EF vs EF-S? Any real difference for my situation?
You probably don't care right now.