I would suggest just browsing through this forum and reading the posts. This question has been asked lots of times and I'm sure you will find some good advice on which bikes fit your criteria. My suggestion for buying used is based upon the fact that since this is the first dirbike you have owned, and your not sure what you want, then you might buy something that you'll grow tired of quickly and want a different one and with a used one, you shouldn't lose much, if any, money by selling it. Plus, your not going to escape the mechanicing(sp?) part anyway with a new bike because the first thing you would have to do is take it apart and grease all the bearings. As far as your pavement requirement, you gotta do what you gotta do but to me, once the leading edges are worn off the knobs, you've lost quite a bit of it's traction and that doesn't take much pavement to do that but maybe a dual-sport would be ok, never tried one. The KLX is actually a good suggestion but if you've never even ridden a bike before(you never said), it may be intimidating to you. But like woodsy said, no matter what you get, sooner or later you will want MORE POWER!
Good luck!