THeThe Canon EF-S 10-22 is a great lens. But even used may be close to $500. But if you can stretch your budget it is a great choice.
<new text added 7/27>
I bought this when it first came out. For ultra wide shots I used to use a Sigma 15mm and correcting distortion. The 10-22 does have some distortion but it is minimal, and in general I use them as is out of the camera unless I am making panoramic photos and need them perfect. What I found when traveling is that the long end of this was fine for typical travel shots, so I never threw my kit lens (18-55) on. This lens lived on my camera, unless I was shooting wildlife and wanted a telephoto. The only thing it . On the wide end you can stand in a corner and capture an entire room. The lens seems sharp in the corners and seems to handle direct sun better than other lenses I have seen. It does come with a flower petal hood.
When this first came out there was a lot of talk that it was built up to L lens specification but that Canon didn't want to make an EF-S L lens. I dont' really know about that, but the build quality has been great, and optically this is better than any lens I own.