I've talked about this a few times before (see related answers at the bottom) but I'll repeat myself.
As you can imagine, checking every pixel against every other pixel would be very inefficient, even if you limited those pixels to the rectangle range that is actually intersecting. But like you mentioned, your second option also has its share of problems.
With that in mind, I'd like to drop two suggestions to solve your problem. The first one is just common practice. The one that really matters is the second:
==================================================
Suggestion #1 - Check rectangles first
==================================================
This suggestion is pretty obvious. Instead of always doing a pixel perfect collision check, start by checking if there's a rectangle-rectangle collision:
- If there is, you'll still need to perform the pixel perfect collision check. In this case it ends up being a little more expensive because of the added rectangle-rectangle collision check.
- But if there isn't, you can return false and exit right there, because there's no chance of any pixels intersecting.
In practice you'll see a large performance gain from this, because the amount of tiles that are not colliding is probably a lot larger than those that are colliding.
==============================================
Suggestion #2 - Use collision points
==============================================
Instead of checking every pixel in the environment tile against every pixel in the character sprite, define a small number of collision points on your character, and only check against those points. This is the approach used by classic Sonic games (see link at the end for more information).
Here's an example. Considering the following information:
Tile Collision Mask

Nothing special here, it's just a mask created from the opacity values of the tile texture.
Character Collision Points

Notice how there are 3 collision points at the bottom, 3 at the top, and 2 in the middle, one on each side. The advantage of having separate collision points is that you can use them for different tasks. For instance, the bottom collision points can be used to detect collisions with the floor, the middle collision points can be used to detect collisions with the walls, and the top collision points can be used to detect collisions with the ceiling.
There's also many other tricks that you can perform with this technique. For example, if only one of the bottom collision points is hitting the floor, you can change to an "out of balance" animation because the player must be near a ledge. Or by varying the height of the middle collision points, you can determine which types of slopes or stairs the character can climb.
Bottom line, with this approach you'll reduce from N x M pixel checks to N x 8 (with the example given) which is almost certainly a lot faster.
You can also define different collision points for each frame of the animation. And by the way you can define a collision point simply as an X and Y offset from the character's origin.
=========================================
Related answers and resources
=========================================