I am a 5 time over AR owner and here is what I can offer you in the way of advice:
AR10 - a nice rifle, and defnately worthwhile, planning on getting one myself, but for a first AR I recommend .223 If you want .308 I can advise other rifle that are more accurate, and in my opinion more fun and easier to shoot.
M4 - without a class three liscense you can't own a true M-4. You will still have a 16" barrel, except 6" of that is a flash surpressor. No advantage to that over the full 16" barrel, which is more accurate. You can have a collapsable stock if you have a preban lower reciever or a fixed Collapsable-style stock on a post ban reciever.
M16 - The AR15 is just the civiilian version of the military M16. The only difference is that the M16 has a Bayonet lug (which you CAN have with a prepan upper) and the full auto capability, which, again requires a class 3 license for civilian purchae.
AR15 - The prefered choice, in my opinion, especially for a first time AR buyer.
Most of my AR's are 20" heavy Barrels. The 16" and lightweight barrels only offer a lighter rifle, which is only beneficial in civilian use during longer periods of standing fire. If you fire from a bench rest, sandbags or bipod I recommend the 20" barrel. A 24" barrel will offer even further accuracy, but I would still recommend the 20" for a first AR. If you decide you shoot the rifle enough, want increased accuracy and want to pay the added cost, then try a match grade 24". This offers a higher accuracy, which brings me to my first question for you...
At what distance are you planning on shooting?
As for stocks, unless you are going to commit the money into buying a preban rifle I strongly suggest going with the Full A2 stock as opposed to a 'imitation' fixed tele-style stock. This will give you more stabliity and the option for counterweights.
The last thing you will need to decide on is the handle, fixed or removeable. I can't help you with that unless I know how you are planning on shooting: Iron Sights, Tactical scope, Rifle Scope?
As for the manufacturer. I, personally, would advise you to stay away from Rock River, Olympic, and all other bargain brand AR's. I am a bushmaster fan, and have found that their product is equal to, if not better than colt, for a slighly lower price tag. In addition to Bushmaster and Colt the other company I would recommend is Armalite, the original designer of the series of rifle. But there you will pay out slightly more than Colt. And although there is an ongoing controversy as to which of the three is better I think that just backs buying a Bushmaster, which can rival (if not beat) the accuracy and dependabily of the other two, with a lower price tag. And the other thing I like about bushmaster is their customer service and quality backing. The one problem I did have was resolved with only the cost of shipping to myself. The way I would recommend Colt is if you choose to buy a pre-Ban. I think thier older products are of higher quality then their current.
Of course, then there are the issues of companies such as Wilson, which can customize or build an AR to incredible specifications, but are not designed for a basic beginner.
As for new or used, an AR is the same as any other rifle; it varies from gun to gun. Some used guns will be well kept and as same as new, except a slightly reduced cost. Just remember, you will get what you pay for.
I hope this helped