Are you looking to keep about the same range of 18-135? I find that my main walkaround lens for a crop body tends to be more in the 17-50 range, plus you gain a nice 2.8 f-stop.
I use the Sigma 17-50mm f/2.8 for this.
However, if you're looking to stick with Canon, you might consider their 17-55mm f/2.8 USM. I've heard people say that if it wasn't a crop-body lens, they probably would've made it into an L lens.
^^^That lens right there is actually scheduled to arrive at my door tomorrow from borrowlenses.com. I'll be able to give you a more accurate review of it after I shoot a wedding with it this weekend. ;-)
So I got the lens today and shot around with it a bit. It's definitely bigger than my Sigma 17-50, but it's much faster and on point with focus. Out of the two of them - if size is the deciding factor - I'd say go with the Sigma. It's got great image quality, and it's pretty small. I'm using the Canon for a wedding this weekend only because my Sigma is starting to misbehave after 5 years of service, but the Canon heavy enough that it's got me looking for my battery grip.
If you have to go with a prime lens to conserve space or make the camera smaller, I recommend going with something on the wide range, such as @pfunk's suggestion about the 24mm pancake lens. That thing is so thin it's almost not a lens at all, but more like a camera body cap.