Look at spatial hierarchies like quadtrees or binary space partitioning (BSP) trees.
These data structures are independent of C#/XNA. The basic idea is like what you mentioned: They involve many small bounding boxes. However, you don't have just a list of small bounding boxes, but instead build a tree structure where every node of the tree represents a bounding box and every branch of that node represents even smaller bounding boxes.
For example, a quad tree works like this: Start out with one giant bounding box. Insert your objects (for example your pixels) into it. After a certain treshold it will split into 4 smaller bounding boxes. And this continues on. The wikipedia article demonstrates it well.
Instead of checking, say, the bounding box of your character, against each pixel in your texture you check it against the biggest bounding box for your image, then the smaller ones contained by it and so on, until you finally you will arrive at a node in your tree that contains only a few pixels to check against, which you can do efficiently.