Friction is generally not independent of area of contact. That's an oversimplification used in introductory physics, and it's generally fairly accurate for hard objects sliding against each other, but when you get into complex situations like modern tires, both the contact area and the shape of the contact patch matter.
In addition, rolling resistance is yet another phenomenon that is independent of ordinary sliding friction. A wheel which is rolling is not sliding, so the sliding friction formula does not apply. Instead, rolling resistance has more to do with the deformation of the wheel and surface, and the energy needed to cause that deformation. As a result, a wheel which deforms less will have less rolling resistance, leading to the tire pressure dependence you talked about.