About a year ago, I was making the same choice as you. I programmed in BASIC, and 6502 assembly (Commodore 64), but that was more then ten years past (blame Windows). I wanted to stick with Assembly, since the microcontrollers only have a few K of memory. I first started downloading data sheets, and looking over the instruction sets and features. Then I went shopping to see the prices of the chips, programmers, and software. I only had USB ports unused, and didn't want to be swapping cables. Atmel came out with a USB programmer (AVR Dragon $49), which was in the price range. The AVR instruction set was most familiar, and kind of like 32 working registers, around 130 instructions. PIC has 36 instructions and one register.
I went with the AVR chips, mostly use Tiny13 and Tiny2313 for LCD projects or just more I/O pins.
The Assembly program went good in the beginning, but lately I've been wanting to do some timing critical stuff, and I'm a little sloppy... So just started learning Bascom AVR BASIC. It's different from the old-style BASIC, but starting to get it together.
Pretty much any microcontroller will work as well starting out. They have similar function and features. If use a high level language, you wouldn't even notice any difference. I'd suggest searching the web for 'projects' related to various PIC or AVR chips in your price range, and see which ones you would like to eventually be building.
I just bought 25 x Tiny13v from Digikey for $0.88 each. Pretty good 8-pin chip, rugged and reliable. I've yet to kill one, and have used (abused) a bunch learning this stuff over the past year, very forgiving chips.
The AVR Dragon is a good programmer, but should mention that it comes at a minimal. You only get the basic board, and need to buy some header pins, jumper cables, and ISP/JTAG cables, and a ZIFF socket. A little soldering. So far, all software has been free to download, and fully functional. BASCOM AVR only has a limit on code size, but its 2k (same as the chips I actually use).