26 or 29 and type to buy?

Matt B,
The size of uni that would work best for you really depends on how fast your dog likes to travel. Assuming a comfortable cadence of 110 RPM the uni speeds would be 20" ~ 6.5mph, 26" ~ 8.5mph, 29" ~ 9.5mph, 36" ~ 11.8mph.

I was in the same situation as you, I rode a 24" as a kid and after a 50 year break I picked up a 36’er" a little over a year ago specifically for road riding. It has worked out great and I’m glad I did not get anything smaller. For road riding and covering some distance and 36’er is hard to beat but I do not have a dog that has to keep up with me.