Chiming in to report on my first world. I explored 3000 blocks south, 1500 blocks west and east (and a bit north of both), and maybe 750 blocks dead north of spawn.
So far I have found no limestone, chalk, or bauxite at all! And my borax has been fairly light. What I have found is endless amounts of conglomerate and granite. Since all I care about right now is bauxite I've started "prospecting" for it. The way I do that is by digging two dirt blocks down, looking at the topmost rock, and running another 200 blocks to repeat the process. Every single time I just find more granite and conglomerate, and I think it would be rare to find bauxite underneath those?
People have suggested changing the rarities of the rocks but I don't think that solves the problem. It just changes how many players will hit a wall and quit when their world is starved of a critical resource. That solution is already used for clay and fire clay (I don't see anyone complaining about those) and I don't want to see exploration totally removed from the game.
Instead I think we need more plan Bs. Which I think fits the survivalist design of the game - make do with what you have. Maybe lime is the easiest way to make fast leather, but if you can't find it and you don't want to strip mine a beach then maybe wood ash can get the job done and it just takes longer. No one wants to build a bloomery or charcoal pit (basically) to make leather so that's your motivation to look for lime first. Likewise for the steel problem I'm currently facing there's got to be another way. I don't know anything about historical steel making but I can't believe bauxite is strictly required. Maybe bauxite makes fancy refactory bricks with 90/95/100% durability, but could granite bricks also work with 50% durability? I mean if I can make the coffin in the center of the cementation furnace out of granite then why not? I also have enough iron to build the walls of the furnace out of iron plates, which is ridiculous. So why not let me? When life gives you lemons make lemonade.