Mostly paved bike paths a few miles here and there with my kids (4 and 6) on their bikes. Smooth, but lots of hills.
Anything that fits, has reasonably-tall gearing and smooth tires would be fine. As I do in most of these sorts of threads, I recommend an old ('90s-era) no-suspension mountain bike, with the knobby tires swapped out for slicks, but almost any style of bike will do as long as it fits. Regardless, it shouldn't cost much more than $100 or so per bike.
Don't worry too much about brand names, as long as you avoid any Target/Wal-Mart/Sears brands. Look for stickers on the frame that specify its material as something other than "hi-tensile" or plain old "steel" (in other words, anything that's cro-moly, aluminum, or a named/numbered alloy is good). Surface rust is okay, and I'd much rather have a rusty Reynolds 531 or Columbus frame than a hi-ten frame with perfect paint.
Other than that, check the bike over to make sure all the components work, or if they don't, negotiate down the price and plan to fix it yourself (nothing on a bike is too hard to DIY except maybe repairing a frame). Regardless, plan to re-grease everything (not just chain, but bottom bracket, headset and wheels hubs too).