Not necessarily. If anything, road tires can feel the best on the road because they can have tread designed to not squirm on pavement.

As far as tread goes, you want something that's not designed to dig in to soft surfaces, as this will just waste energy by deforming against the pavement.
At the centerline of the tire, you want the tread to be basically smooth. Some tire manufacturers add small shallow ribs or ruts running parallel to the direction of motion; this is fine, and can serve as a wear indicator. You do not want the centerline to contain tread patterns that run perpendicular to motion.
There are different ideas as to what the edges of a road tire, the contact region during cornering, should look like. Some manufacturers leave it smooth, which seems to work fine. Some manufacturers put fine shallow criss-crossing file patterns there, with the intention that they'll interlock with road irregularities to improve cornering grip in wet weather, which also seems to work fine. Some manufacturers space shallow diagonal ruts along the edge with the notion that they'll shed water to prevent hydroplaning, which is completely pointless because you'll never manage to hydroplane your bike anyway, but it's harmless and makes for road tires that work fine. You do not want knobs along the outside, as these will squirm on pavement and make cornering feel less confident.

Another factor on tire speed is suppleness. Tires deform as they roll, and deforming stiff tires wastes more energy than deforming supple tires.
A typical way of guessing the suppleness of a tire's casing is threads-per-inch (TPI). Using large numbers of fine threads instead of small numbers of thick threads allows for suppler, thinner casing. So, higher TPI tends to be better. Typical TPI values for clinchers are ~30, ~60, and ~120. However, there are some caveats to how it's reported and what it means. For instance, some manufacturers add up all the threads in multiple fabric layers, so "180TPI" can actually refer to a triple-thick layup of 60TPI. There are also sometimes big differences in how the threads are layed up: Panaracer has a standard 120TPI casing, and they have an "extralight" 90TPI casing that uses the same threads as the 120TPI casing but with finer spacing, so the 90TPI casing is actually lighter and suppler than the 120TPI casing. The point being, don't judge things just on TPI.
Other factors in tire stiffness include tread thickness and the use of puncture-protection belts.

As far as size goes...
...rims can fit a wide variety of tires sizes. With an internal width of 19mm, you could probably shove 2" MTB tires on those rims without any real issues. If you're interested in going larger, the real question would be how much clearance your frame and brakes have.

As to what size would be optimal? Going wider means better capacity to run low PSI without problems, which can be faster and more comfortable over rough surfaces, and improves cornering stability. Going narrower means small reduction in wheel weight and a bit of aerodynamic improvement.
Don't expect a huge amount of paved performance difference to come strictly from width, though. I have one bike with 23mm Bontrager R3 tires and one bike with 53mm Compass tires, and they perform about the same on level pavement, at least when I'm solo riding in the ballpark of 20mph. At higher speeds I'd guess the wide tires would start to fall behind a little due to aero, although I haven't ever cruised much faster on that bike except in a paceline.

//===========================

As far as recommendations?
Continental's GP4000SII is and excellent road tire and is available up to 28mm.
Continental also makes Gatorskins which are somewhat more puncture-resistant at a bit of penalty to weight and rolling performance, they're available up to 32mm so you could switch them in without changing width.
If cost isn't a factor and you want tires that are very light and supple, you could check out Compass tires, which are manufactured by Panaracer. They're available in a very wide range of widths, and are an excellent option for wide high-performance tires.