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.