The distance depends on varieties, environment, and mechanization.
Usually we need enough space for canopy and root, but for some species/uses (nature has always exceptions), where one look for depth roots or higher canopies, in such case they should be less space. If your fruits tree has fruits on side, usually you need enough space for canopy (if you are not looking for wood [some fruit wood is very valuable for building stuffs] or preparing rootstocks).
There are many rules and calculations: larger canopies: more leaves, but also less shadows, so more fruits/better fruits. On the other hand, if it is too much expanded, you will have less fruits per square meter. So there are many theories about what it is the optimum (which depends on species, but also on next factors). [Note: height is also a factor, so by pruning on height, one could still have a denser orchards but still not so much shadow.
But climate is also important: in part this could enlarge roots space, e.g. in dry places (so see previous point): on many fruits, one doesn't look for a dense orchards, but healthy fruits. So less shadows and less denser branches, so that diseases (mainly fungi) could not effect the quality of fruits, or health of trees. Rain and wetness (fogs) requires larger distance.
For dry places, one need more space (so more roots) or the inverse if there is an irrigation: because cost of irrigation, one would use denser orchards. Fungi diseases should be a minor problem on dry places, and less production is balanced out of less costs (irrigation infrastructure and water).
Mechanization (or in general handling of tree, in case of small fruit tree garden) is also a factor. You doesn't want to use ladders, so a compact orchards is ok. look if you want also to use the space in between trees (e.g. to walk easily).
So at the end, I think you should ask the people who sell you the rootstock: the rootstock is climate specific, and it "decides" how large the tree will growth: there are good rootstocks for small trees of apple, peaches, plums, etc. (but I didn't find good one for small cherry trees). And as vegetable garden, if one plants tree not on square, but on triangle (so on next row, trees between tree on previous rows), you can gain some space.