Well you could still use Rectangle’s if you want. Instead of determining it all mathematically, you can do it like this:
In whatever collided method you have for testing, have it return a list of some kind that contains all collisions that occured. This way you can have different cases for colliding up, down, left, or right. (like in Mario, for instance, colliding down on something means it’s dead, whereas left or right means you are dead) Now, instead of using a single rectangle for testing, use four, one for each direction. The up rectangle should be the character’s (x,y-5,width, height/2) so that it has a slight buffer zone (5 pixels) and tests all upward collision. The other directions are the same way. You can experiment with different buffers for more accuracy or ability.
(I usually create constant int’s called UP, DOWN, LEFT, RIGHT, then put them in the list if each kind of collision occurs, and test for them again later)
This method works just fine, although I’m sure it’s a little inefficient. I made a Mario clone a while back where I was originally using coordinate testing (like you), but that created problems which immediately went away when I converted it to this method.