Here's my understanding (based on lots of Russian travel): You can legally explore anywhere in Russia, except keep the following in mind:
1) Don't forget about registration requirements. If you're moving around a lot, this is likely a non-issue, but keep all your bus/train tickets, etc. If you're using a central hub city for radial day-trips, register in the hub city.
2) "Closed cities": Some cities require a permit to get into (typically ones with sensitive military-related industry). I don't know whether it's possible to get a permit unless you e.g. have a close relative there. Some cities (e.g. many cities in the north of Krasnoyarsk Krai) are closed only to foreigners, so locals may not know they're "closed". There's a list here: https://en.wikipedia.org/wiki/Closed_city#Russia
3) Border areas. Unless you're in the process of legally crossing the border via an official crossing point, you need a border area permit to be there. The permit is possible to get but takes a long time (around 2 months). Note that in some areas (e.g. in the Arctic) some areas may be defined as "border areas" despite being thousands of kilometers from the actual border.
4) Due to recent political tensions, I would STRONGLY advise to stay away from anything that is even remotely related to the military or any sensitive industry, especially if you're carrying a camera, GPS-capable phone, etc. Also, stay well away from any remote place with especially luxurious houses / "dachas" that appear to be well-guarded.
5) Some nature reserves have areas that are forbidden to enter (or forbidden to enter without a special permit) for reasons of nature conservation. These are usually marked.
With all that said, seeing the little remote villages of "real Russia" can be very fun and rewarding!