The 555 is completely out of question. It's an outdated design. The maximum possible frequency might be something like 300kHz, but the duty cycle will be far from 50%.
One of the easiest ways of generating a very reliable square wave is getting a crystal and dividing it down to your desired frequency using something like a 4060 chip. It's basically a chain of cascaded D flip flops configured as frequency dividers. Its usual applications are counters, but I found them very useful for generating various frequencies for e.g. ultrasonic and optical sensors modulated with 38kHz or what not.
Get a 16MHz crystal and divide it down 32 times, and you'll get a nice clean 500kHz square wave. Moderns 4000 series ICs work fine up to 20MHz without a hitch.
You could of course use a 1MHz crystal and a single flip flop - but these come in quad sets in 16DIP packages anyway, so you're not going to save any space. The 4060 chip is small and extremely cheap, so using separate flip flop is not going to save you much money.