Speaking of Toyota, I think a Matrix would fit your description pretty well. You could even get a brand new 4wd model for under $19,000.
Oh hell no. You don't want a corolla awd. I mean, why put 140hp on awd. Awd requires power to make it effective. I wish they could have made the celica engine version awd!
I suggest looking at Ford Focus. Especially the new ones. As of last year I think Ford put the Protoge engine in the Focus. It's a pretty nice car.
I would like to get an AWD car myself. For the US that pretty much limits you to Suburu and Audii/Volkwagon. If I could get my hands on a Mitsubishi vr4....
Now, where do you live? Is rear wheel drive out of the question for you? For me I don't even want to look at rear wheel since I want something that handles in the snow.