I am looking for sandbox-y random encounter tables, ala D&D 2e, where you had "Hills," "Mountains," "Jungle," etc. In other words, Challenge Rating should not be considered, but rarity of creature should be. I believe previously this was a d100 roll. Where can I find some, in the rulebooks or elsewhere?
Storm King's Thunder has this sort of random encounter table on page 69. You roll a d% and consult different columns of the table depending on the environment your party is in - Forest, Grasslands, Hills/Moors, Tundra, ect. However, since this is an adventure about giants, the table is heavily biased towards encounters featuring giants and Uthgardt barbarians (who hate giants and anyone allied with them).
Dropping a random encounter into a session is more realistic than having the heroes jump-cut to the dungeon, but it puts the story on hold while the heroes have "just another battle." Unlike previous editions, 5e prefers to focus on the narrative of the PCs rather than simulate a realistic world, so if you want this type of table, I suggest you convert something from a previous edition or write one tailored to your campaign rather than try to find one in official 5th edition products.
Volo's Guide to Monsters has a series of tables in Appendix C, wherein creatures are broken out by terrain types. They are not weighted for rarity, so they are more for generating ideas than a roll-based random encounter.
Also, although they only include creatures detailed in Volo's Guide, many of these are just subtypes of common creatures in the Monster Manual, so it is a decent place to start creating your own.