The question you have to ask yourself is what is the length scale of the features you want to study as this will inform you of the correct technique to use.
The most common type of SPM is the atomic force microscope (AFM) which has an astoundingly high resolution (atomic scale in the right conditions), but as a result is limited to relatively small scan sizes with the largest avaliable being about 150 x 150 µm. There are AFMs that can stitch together multiple images and give you massive images, but as you said collection time will be very very long (if this is what you want to do, look for an AFM in a clean room that is primarily used for metrology in silicon wafer processing as these generally have the software to do the stitching).
If you only care about microscale features, then a stylus profilimeter would do the trick. It is basicaly a large AFM so it has most of the same advantages/problems. I haven't really used these so I am not sure how well they image or if they are mostly used for single line profiles.
Better than a stylus profilimeter, in my opinion, are the suite of 3D optical profilimeters. There are lot of options here from different manufacturers using different technologies, but they all have similar characteristics: xy-resolution is limited by diffraction (depends on objective used, ~200 nm) and z-resolution is sub nm; scans are very quick (can be less than second); can stitch many scans together to form very large images (I have seen an example of a whole coin); they struggle with transparent materials; they can't see reentrant geometry.
If you require nm resolution over a mm scale, I would go with AFM and just take images of representive areas as data analysis would be really difficult if you had to analyse AFM data over millimeters.
Finally, the last piece of advice I'd give you is something all students hate: go read the literature. This is the best way to figure out what technique to use. What I found helpful was to make a table of all the different techniques used in similar pieces of research and make a list of their pros and cons, how easy are they to learn, do I have access, what does data analysis look like etc. Even if you end up using the first technique in the table, you have learned a lot about where and when other techniques are useful.
