I know exactly your situation!
I'd start off with a basic scripting language such as Bash to get your head around the basics of programming constructs (loops, if/then, case, etc). From there you could move into Python or Perl. Python is pretty simple to learn, and there are hundreds of great resources out there for free.
As far as what programming can do for you that you can't already - your imagination is pretty much the limit. You can write some pretty cool tools for security auditing, practise exploiting software (with permission of course), and distributed testing of network objects just for starters. And because languages like Python and Perl are available for just about every platform, your new skills will be transferrable.
For those who have been in the industry a while, it is interesting how the "security" role has changed (some people I know call themselves security professionals because their role is mainly updating AV definitions and performing routine scans). Don't feel like an idiot now for not getting into programming earlier - plenty of time for that when you're knee deep in home-grown programs that make you're life easier (i.e "Why didn't I start this like 10 years ago)