My only caution with the Crosscheck: They are really nice bikes, and quite versatile, but they're heavy (something to keep in mind if you have to, say, carry it up a flight of stairs or something), and they seem to run really long in the top tube.

As for the pedals, I'd go with the Fortes. They are a little grippier on the platform side, and IIRC they should take Shimano cleats.