When I had this question, I went for the Tokina 12-24F4. Sometimes, 12mm isn't wide enough on my crop bodies, but this is rare.
I also have the Canon 24-105L, and I can tell you that it is a very sharp lens, especially at the wide end.
The reviews of the 15-85IS are variable. Some have it sharper at the long end in the corners, and some have it sharper at the wide end. You do get lots of vignetting and distortion at the wide end, something that I now can avoid with the Tokina and the 24-105L combo.
If you want sharp corners at the wide end, you may consider the Canon 10-22. It is not an easy feat to find a lens this wide that will give you sharp corners at 10 mm.
My 18-55IS did pretty well in the corners outside, stopped down. Wide open, there was too much distortion at 18mm, too much vignetting, and 18 is not wide enough sometimes. It is here that an ultrawide will help out.
What do you want to photograph, and how often? If you have a frequent want to shoot architecture, I'd want a real ultrawide.