CAD first is a good idea. If you can get your CAD down, then get some basic CAM software. Actually, if you can do the CAD then the machining software is quite easy to use at a basic level (easy to use, hard to master
)The other way to go is to just get the CNC machine and outsource your programming, though you need pretty specific reasons for that one. It's not a money saver, generally, to buy a machine and outsource programming (compared to just buying the parts you need), unless you've got need of a lot of parts. Still, in some cases that's the way to go. I do contract programming for some router manufacturers who offer 'turnkey' solutions to customers. The customers send me all their parts, and then the company delivers a machine already programmed to cut their stuff.
And, finally, as a general rule router manufacturers lie through their teeth about the capabilities of their machines. Either find someone using the machine you're looking at for the purpose you're looking to use it for, or find someone who really understands machines, and get a second opinion before you set your expectations based on what the sales people say. (or do a lot of reading on CNCZone, though I find there's a huge gap between guys on there for hobby stuff and the professionals. You can find loads on really accurate and fast machines, and loads on really inaccurate slow machines...but there's little talk about the stuff in the middle, relatively speaking)
