I wouldn't worry about supplies of the game itself on Tuesday. This is a much different beast from a console launch - those dvds are easy and cheap to press out large quantities. I remember that for Halo 2, I didn't pre-order, just walked into a Best Buy when it opened at 10A. And there was a separate area where they funnelled through the Halo purchasers. It was busy, lots of people walking through, but there wasn't like a wait in line or anything like that. Since I had no Halo 2 supply problems, I doubt there'll be Halo 3 problems - while Halo 3 will in general be more popular than Halo 2 was, at the present time the 360 console base is smaller than XBOX was at Halo 2 launch.
Anyways, I bought a console yesterday at a Best Buy, just to ensure I don't run into any issues there, and I asked about a special Halo 3 sale time on Tuesday. They said they didn't have any. So definitely call.