Joel: First off, welcome to the forum.
Just a few thoughts about the RE.
For a new rider, I don't think there is a better bike out there and for the speeds your mentioning, the G5 is the way to go.
It has a slightly different frame than the B5 and C5 so it is rock steady at those speeds.
More importantly for right now, all of the RE 500's have more than enough power for city riding without having so much power that it will get you into trouble.
(Some of the more powerful crotch rocket bikes tend to be very "peaky" with docile power up to a certain rpm and then "HOLY CRIPES!!" The RE tends to start off with more than enough power and it smoothly just keeps on pulling up to the next shift point.)
Speaking of power, I haven't ridden the 250cc Cleveland bike but I suspect it lacks low speed torque so to get any real power out of it, it will need to be reved up to high rpms a lot..
The RE on the other hand is Pure Torque right from the start.
Although its horsepower is limited by its long stroke engine it still has enough power to keep it from becoming boring after you get a lot of miles of riding it.
IMO, except for the 883's, all Hardly Davidson's are way too heavy and if a guy gets a 883, most Hardly riders will frown at it and tell you that "only a girl will ride a 883".
Anyway, I've owned my G5 for almost 2 years and 9600 miles.
Except for replacing the rear chain, a few light bulbs and the fuel level switch breaking it has been 100% reliable.