Does that make sense to describe how our travel was rushed therefore couldn't fully enjoy what the cities have to offer?
It is an idiomatic use that is reliably understood in the manner you suggest: that you only had time to see or feel a few aspects of the cities.
Skim = to read or look at something quickly to understand the main points, without studying it in detail:
Several dictionaries of idiom show “skim the surface” as something like:
skim the surface (of something)
To do, engage with, or understand something to only a minimal or superficial degree.