What kind of plane is good for this type of flight?
The cheap kind. Joking aside, the exact airplane to use depends on the size of the banners or billboards you're going to be towing, but generally speaking you want something reasonably rugged, with good slow flight characteristics, sufficient engine power to be able to overcome the added drag from the banner, and, hopefully, some decent fuel consumption.
I'm not entirely kidding about the cheap part though; banner towing is hard on the airplanes and carries a higher-than-average degree of risk, so you do want to stay away from airplanes that will be expensive to fix, if you can help it.
As for specific types, I've seen banners towed with everything from -152s to Grumman Agcats; a large banner tow operation apparently had a Super Cub with an O-540 bolted to it, so you'll see a ton of different things, but tailwheels seem to be the norm, at least in the US, and many outfits will make additional modifications such as removing engine cowlings to help with cooling.
With banners they appear to be flying slower than usual. Is this just an illusion?
No, they are indeed flying slower. First of all, the added drag from the banner slows the airplane down all by itself. Secondly, you're being paid to advertise, so you want to make sure that people can read whatever sign you're towing. You're not flying the ragged edge of the stall (it's dangerous, uneconomical, and unnecessarily hard on the engine), but you're probably going to be flying on the backside of the power curve.
What are the practical or regulatory requirements that the plane must meet to be capable?
In addition to the practical considerations we've talked about above, banner towing operations require a waiver from the FAA. The company has to apply for it and every pilot must be trained in banner tow operations, pass a review from an approved FAA inspector (who will be watching you perform picks and drops from the ground), and be added to the waiver. The aircraft and tow hitch mechanisms also have to be inspected and approved for banner tow operations, and added to the waiver.
Here is the current FAA Banner Tow Information handbook, covering equipment, operations, waiver information, and other assorted miscellaneous if you're curious to learn more.