So my understanding is one needs smaller wheels to accommodate the higher sidewall, else there will be rubbing issues as the tire will be to big to fit in the wheel well.
Your understanding is correct. Typically you can deviate from the stock tire size by one size, up or down, in width or aspect ratio. From what I'm seeing, the stock size is a 225/55R18, nominally 225 mm wide, with the sidewall being 55% of the width. There are sites, such as https://tiresize.com, that will show you a list of tires that are of equivalent or comparable size.
A tire in the size of 215/70R16 or 215/75R15 would be the same diameter, so you would not lose any power, and you would not need to recalibrate your speedometer. (There are few, if any off road tire options in the 225 width, and a 235 width would most likely work, but a wider tire has a higher chance of rubbing, though if you keep to the stock diameter you should be fine.) Off road tires usually have higher rolling resistance, so your gas mileage will probably get worse. You would of course need new 15 or 16" wheels, and they would have to be aftermarket, as OEM Subaru wheels from another car will most likely not fit over your brakes. There are many companies that sell wheels in the 5x100 bolt pattern you would need, but it's worth giving them a call to verify their wheels will fit over your calipers.
There are plenty of All Terrain and Mud Terrain tires in both of the sizes mentioned previously. You probably do not want Mud Terrains, as they will be much heavier than the stock tires, loud on the highway, and pretty terrible in snow. I run a set of General Grabber AT2s on my lifted 2006 Forester and I've been very happy with their performance. They've been phased out now and replaced with the ATX. People also seem to like the Toyo AT3s. The Cooper AT3 4S, Yokohama Geolandar AT GO15, Falken AT Trail are all a milder AT tire that will be more road oriented. The BF Goodrich K02 is an excellent tire, but almost certainly too heavy. It is worth trying to keep the wheel and tire package weight close to the OEM wheel and tire package weight to keep performance relatively good.
If you follow this advice, you should have no issues fitting off road tires on a stock Crosstrek. If you lift it, the company that made your lift will most likely have a chart showing what tires fit without rubbing. Often you can go up two sizes with a 2" lift, but the lift supplier will know. Larger tires will impact your speedometer, but tiresize.com has a calculator for that to see if you need to be concerned. You will also lose some engine power, but when I went up one size (215/60R16 to 215/65R16) I didn't notice a change.
And finally, I haven't had any problems at all. With AWD and AT tires, I haven't been able to get it stuck yet.
