I think the 16F877A would be a great choice if it is easily available but it is a giant step back from where you are with the newer chips. I started with that chip 15+ years ago and I rather like it. I liked the 16F628A even more.
At the time, there wasn't a decent C compiler and even today, I would have a tendency to write in assembly language. The learning curve is a little bit steeper but debugging is actually easier because the output of C compilers can be difficult to understand. Plus you will see a lot of code dedicated to banking and paging. The careful assembly language programmer can avoid most of this.
As to which toolchain? Load them both and experiment.
Since you are using Arduino, you can always program that chip in assembly language or C without the overhead of the Arduino infrastructure. You would use the avr-iibc library and the avr-gcc compiler and you already have them because that's what Arduino uses. This allows you to get right down at the hardware level and the ATmega328P is a very nice chip. I prefer the ATmega128 because it has more pins but, either way, these are great chips to work with. I definitely prefer the AVR architecture over the mid-range PIC.
If you want to program the device with ICSP (In Circuit Serial Programming) using avr-dude (Arduino uses it so you already have it), you don't even need to use the Arduino IDE or the bootloader. You can get right down to the bottom in terms of firmware and hardware. I find this easiest to do under Linux using gedit as the editor and Makefiles. It's a very nice environment. I haven't had a lot of success with debuggers so I tend to avoid them.
I first bring up the serial port, then I add some conversion routines (copied from "The C Programming Language" by Kerrnighan and Ritchie) and this gives me serial output for debugging. The K&R code doesn't assume a "heap" and I really don't want to get involved with things like malloc() on a small chip.