Why do bird's red blood cells have nuclei but mammals do not? Birds are often smaller than mammals, wouldn't they have tiny capilleries the rbc would need to squeeze through?

About the avian circulatory system:

http://people.eku.edu/ritchisong/birdcirculatory.html

The lack of a nucleus in human cells is not so that they can fit through capillaries. Bigger cells also fit through capillaries. It is to increase surface area of the cell available for oxygen absorption. But

Yes, there are very small mammals out there, and even smaller fish, amphibians and lizards and these all have blood celles with nuclei, so size isn't an issue.

So the corollary of the above would be that birds are more efficient at absorbing oxygen into red cells (or their hemoglobin has a greater avidity for oxygen) than mammals hence the selective pressure to loose the nucleus and thus increase the surface area for absorption was far less of a factor. Is there any evidence for that?

Well I'd say that birds might have evolved a different route to the same overall outcome. Mammals have a nucleus free RBCs meaning these are more efficient at transporting oxygen. Birds don't but do have the airsac system (as indeed did some dinosaurs and pterosaurs) which would have made gas exchange more efficient.

Bird respiration is more than twice as efficient as that of mammals, which is part of the reason that some birds can sustain powered flight at altitudes higher than most humans could survive even if lying still.