I had (something) of the same problem in one of the games I posted recently. Basically, instead of just doing an 'exact index of collision' style thing, I figure out a range of possible tiles that the character could collide with depending on the direction of the motion. This allows you to have variable sized entities, with little worrying about tunneling/missing edge collisions.
If it's falling/jumping I iterate through the horizontal tiles (left most tile to right) first, then move up or down depending on the direction in question and for some predetermined 'limit'. The only 'important' tile in such checks is the highest/lowest (depending on which direction you're moving), and it's fairly easy to construct the loop for this.
If it's moving horizontally, I iterate through the vertical tiles (From top to bottom) starting from where the entity's head is down to the tile its feet are located, then iterate left/right to some limit. If the tile's bottom is located below the entity's top, it's a possible collision object or if its top is located above the entity's bottom (Like regular AABB style collisions, hah).
In both cases, only the most extreme object in a given direction typically matters for the purposes of a collision. The limit is predetermined based on maximum speed of the entity in question. After you find the tile in question, you either move the entity or calculate where the entity will move to, if it's further than the object's extreme edge then you've got a collision to handle.
For the most part, this'll help to avoid the whole fun of 'tunneling', and if you should only have to check a small (Relatively, based on size) number of tiles for the collisions. I know that it means very little, but I tested it out with the platformer that I made, and just dumped numerous semi-randomly moving entities into it and didn't detect any sizable difference in the frame rate (Though that might be more of a "You've got an alright computer" than "Your algorithm was good" sort of dealy).
This method was done resolving X then Y collisions, if you want to try to resolve them together, you can use a line algorithm
to plot the player's path through the air in a straight line, then create a path through that line (Find the line, then figure out the tiles you'd move through to follow that line) for the limiter.