I bought a Vodafone SIM on the street no problem. I briefly looked at CAI and again at LXR but did not see a vendor selling SIMs inside either airport. (Granted, I only had access to a tiny part of CAI...the F and G gates.)

There are two or three other prominent providers...service has been good for me everywhere, all the way down to near the Sudan border (Abu Simbel).

There are phone shops practically everywhere...even in some of the little towns on the road between Luxor and Aswan. Bigger cities have them everywhere.