I know I don't always agree with his conclusions, but I'd like to hear what Streak Eagle has to say about the Phantom's envelope - from what I understand, he's researched the hell out of it. For that matter, on the deck, you're going to have more "g" available with denser air moving over your control surfaces at any given speed. Your "g" authority, both sustained and instantaneous gets lower, or requires higher speed to reach, at higher altitudes. It follows that if an F-4 can perform a 7g+ turn at, say, 450KIAS at 20,000 feet, it can most definitely yank that same "g" at low altitude. As can a MiG-29 match an F-15C's 9g turn at low or high altitude.
Also, how are your aircraft loaded? "g" limits change for any number of reasons, not the least of which is loadout and weight. If your jet is flying with external tanks, or high internal fuel quantities, its placard limit is not going to be the same as the actual limit at that weight.
To make it easier, say we have aircraft X. Aircraft X's placard limit is 7.3g - say this is at a weight of 45,000 pounds. If aircraft X is loaded to 50,000 pounds, its "g" limit is 6.5g. At 55,000 pounds, its "g" limit is 5g. As weight burns off (either as fuel, or weaponry) the limit increases back to the structural placard limit at 7g. Every airframe, for the purposes of making it last for a long time, has this same "changing" g-limit due to weight/loadout. Also, if tanks are loaded, the limit can drop enormously. I recall reading an unclassified report from an exchange pilot on the MiG-29, indicating it only has a 4g limit while the centerline tank is installed and still carrying fuel. Good luck fighting an F-15A, C, E, or otherwise anywhere with a 4g limit, and an alpha limit as well in that configuration!
(EDIT): That limit is also a symmetric "g" limit. Rolling limits are slightly or sometimes significantly lower than the symmetric limit, because the aircraft has differential "g" being loaded on the airframe during rolling and pulling maneuvers.
Of course, in air combat, I can't think of any pilot who would follow "g" limits religiously if his/her own life, or that of the crew, were in peril. If you need to put on a 10g or 12g+ instantaneous turn to get out of the way of that missile, or to exchange energy for turn performance to kill that enemy who has been trying to kill you, you do it. Better to bring back an airframe with less available hours of flight remaining than to sacrifice the life of the aircrew because of some line on a chart, and I think every pilot I've spoken to who has been fired at has told me just that.
We must also remember that "g" and "g" limits aren't everything. I've been fortunate enough to talk to a good number of F-14 drivers and RIO's who were, or rode with, excellent sticks that mastered slow speed BFM/ACM. Constantly loaded up on alpha, and rarely getting up to or higher than 3g once the fight slowed down, they'd mercilessly beat smaller, more nimble aircraft that didn't handle as well at such slow speeds, due to their higher wing loading, or where their pilots were uncomfortable flying right at the edge of stalling. One of those pilots I had the pleasure of speaking with would do the same thing in the F-4D as a AF Reservist against F-15 drivers (A or C), and come out on top at high or low altitude.
But more than the plane, alpha or "g" limits is the pilot. The better pilot, who knows his/her own plane AND the enemy's, who understands the advantages and disadvantages of each airframe, is going to have the advantage in a dogfight. This was said earlier in the thread, I've said it before myself, and I will never be of an opinion otherwise. Pure fighter performance? I'd give it to the MiG-21 across the majority of low to mid-speeds in a turning fight, with the F-4 just catching up at higher subsonic speeds, but never really exceeding the MiG-21's turn performance. In the vertical, the F-4 seems to me the better candidate.