Surprised your new house doesn't have at least Cat-5e runs pre-installed. Even houses built around 15 years ago usually used Cat-5e for for telephones/patch panel.
My previous home (now a rental) is a 1970s build, and had horrible power sag issues (killing one of my PCs when I foolishly powered it on without a UPS). When I got around to changing out all the AC conduits, I went ahead and dropped Cat-6 for each room. It looks fine enough that a wife won't complain, since it's just another wall plate. In my current home which is a 1950s ranch style house, I got lazy and just have Cat-6a tacked to the floorboards since I intended to move back to the previous house later. Thankfully I haven't gotten many complaints since it's mostly in my home office/backroom and the main bedroom. My run to the garage is going through the attic so it's unseen.
Dropping cable runs isn't really that hard, and certainly you'll be more than capable of doing it yourself. If you'd like you can hire a local electrician or IT guy who do drops. Usually they won't charge an unreasonable amount for each run. Then each run will just be wall plated with a jack. Sometimes you can negotiate with them for just the drop to be done to save money. Termination doesn't take too long.
While you're at it you can have the APs installed on the ceiling too