You can use the avr-objdump utility with the -S option (I think) on a .hex file to disassemble your sketch. Using it on a .elf file will let you see your C++ inline with the assembly. Can't recall that option off the top of my head.

I've used this site: http://www.kpsec.freeuk.com/components/cmos.htm
It has a listing of a bunch of common 4000 series CMOS chips.

then have your Arduino drive its own RESET low to reset itself.

I'm too lazy to double check this now but I seem to recall attaching to your own reset line is specifically "prohibited" by Atmel. Or maybe it was something else...

Maybe it was having something on the reset line when using the AVR Dragon or a similar debugger? For those, Atmel says the debugger needs full control of the line, and having a capacitor or something else on it will bugger with things.

How can I get the bootloader on the actual microcontroller to accept a 20Mhz crystal to I can upload sketches through my USB port as I used to?

The bootloader has no control over clock speed. Just swap out the 16MHz crystal for the 20MHz, and the ATmega will run at 20MHz. The bootloader has no way of telling what speed it is running at so you don't need to worry about what speeds it will "accept".
One thing you will have to watch out for is that the different clock speed will mess with delay, delayMicroseconds and millis.

You could use a shift register, or an I/O expander, or come up with a trickier way of multiplexing.

You can use a transistor to drive the LEDs, as you said. A transistor is essentially the same thing as a relay, except that relays isolate the switching and switched current/voltages. But since LEDs run on DC and are similar voltages anyway, a transistor would be just fine. There's some schematics for that in the playground somewhere.

If you've got the LEDs on a different chip, you'll have to make sure that chip can source all the current nesseracy to drive the LEDs, not the Arduino. You could also use transistors to switch the LEDs and you wouldn't have to worry about what the chips can provide for the most part.

The code you write in the Arduino environment _is_ C/C++. Simple as that. It just comes with a bunch of predefined functions and libraries to make everything easier. All the code is there if you want to look at it. The projects that are created all have cpp files somewhere in the project folder. All the Arduino environment does is refrain from displaying some of the #includes and the main function of the project's code... so it's all there, just not explicitly in Arduino.

You can still compile all the sketches from outside arduino using the avr-gcc tools and rot from the command line, or with makefiles.

You can use C++. In fact, a couple of the libraries around use object-oriented programming: Wire for one, and some of the LCD libraries. The hardware Serial interface also has its library written in C++.

There are some tutorials on C and C++ on the bottom of the tutorial page that might help you with the language. Check your local library and see if they have any books on learning C++ as well.

The Arduino software comes with avr-gcc, an open-source C/C++ compiler, so you don't have to worry about that. That should be enough to get you started. (: