Your priority should be training, if you don't have much pistol experience. The recommendations of a .22LR have some merit, but .22s are poor dual-use pistols (great for target practice, but not great for defensive use!) Therefore, I would recommend something in 9x19mm. Nine millimeter pistols are good for defensive use, and are some of the cheaper service caliber pistols to feed. That said, your budget really needs to support $25/month or more for effective practice with a 9mm (100 rounds, minimum, IMO). Also, I recommend getting a laser cartridge and target for improved dry-fire practice.
I would recommend a "Compact" sized pistol or sub-compact that takes extended magazines that form the rest of the grip. The Glock 19 would be the most popular "compact." A Springfield XDS-9 with 8 or 9 round extended mags would end up being a similar size. With 7 round mags, the grip is in the sub-compact range. The key here, in my opinion, is that the extended mags have a base that mimics the grip of a larger pistol, rather than just being a magazine.
For a general purpose pistol, I'd look for a 3.5-4.5in barrel in semi-autos. The shorter the sight radius becomes, the less forgiving they are to small errors in sight alignment...aka, they are harder to shoot well.