I cannot say much about PICs, but most of the time it works the same. I would recommend you to get an Arduino, not a Duemilanove, but one of the new models, Leonardo or Uno. Arduino has really great user base, so if you encounter a problem, you can get your question answered in a few minutes on the official forums. All Arduino boards are programmed in something between C and C++, I think you can do the same with PICs.
Speed-wise, both of the platforms are more or less the same, while there are so many chips that offer so many different configurations you will surely be able to get the one you need. When using the board for development, you will probably use a bootloader, but that only adds a delay when you power-up the chip. With Arduino you can use ICSP to program the chip without using a bootloader, but it is slower and does not add that many advantages as you would think.