The easy way to start in finding reasonable substitutes is to look for other woods with similar mechanical/acoustical properties. Rosewoods are generally distinguished by relatively low damping, high density, high surface hardness, and good stiffness along the grain, so if you're looking for a rosewood substitute that's the suite of traits to pay attention to. This assumes, of course, that the properties that have the most effect on the way the wood vibrates also have the most effect on the sound. This is not a slam-dunk: we can hear some pretty subtle things, and there's always the possibility that some harder to measure property, like the Poisson's ratio, is important. These are physical objects, so the laws of physics should cover anything we need to know: I don't believe in leprechauns.
Anyway, there are a number of woods that are 'local' to me (the USA) that fill the bill. I've spoken of these before on this list, and others, but I'll risk sounding like a broken record anyway.
The samples I've tested of Osage Orange, Maclura pomifera, have been practically drop-in replacements for BRW. It's a common enough tree these days, and is mostly used for fence posts, which are reputed to outlast the holes they're in. It can be challenging to work with hand tools, but the bigger issue is the color, which is very bright orange when fresh. It darkens to an interesting brown over time, but finish really slows that. I have recently had some luck in fuming it with ammonia, which darkens the wood without seeming to otherwise change the properties.
Black locust, Robinia pseudoacacia L., makes a good substitute for Indian rosewood. The pieces I've tested have been somewhat lower in both density and damping than most IRW. It can look very similar to Cypress, but has the rosewood timbre, so the guitar will tend to be a 'Classica Blanca'. It also darkens quite a lot when fumed with ammonia, ending up close to mahogany in value, if not hue. This is also practically a weed where it grows, and a wood that makes very good fence posts.
Oak (Quercus species) tend to have the density, hardness, and stiffness of rosewoods, with higher damping. They bend notably well, as a rule, and I've had good results with all the oak guitars I've made in terms of sound.
There are a number of species I've been wanting to try, but have not as yet. One is Shagbark Hickory, Carya ovata. I recently got some that was well quartered but have not had a chance to measure or work with it yet. If density and stiffness are important, it should be one of the best.
Although there are a number of North American woods that are hard and dense enough for fingerboards, few of them are commonly available and even fewer are black.
Common Persimmon Diosporos virginiana is a member of the ebony family, and is sometimes black is streaks, but usually white to grey-brown. It's similar to Macassar ebony in properties, and is fairly wide spread. Texas Persimmon, D. texana, is more restricted in range, and the trees are smaller, but is said to be black.
I've gotten a few samples of 'Soft Shell Almond' that were fairly dark, and very tight grained and hard. Those of you in California might well be able to turn some up. Other 'ironwoods', such as American hornbeam Ostyra virginiana tend to be light brown or cream color, and must be stained or dyed to work well as a fingerboard.
As James hints, bridge material is less constrained in many respects, and it's not too hard to find substitutes if you try.
The biggest issue with all of this is the fact that people listen so much with their eyes. As the 'Leonardo Project' has been demonstrating, when people can't see the guitars they have a lot of trouble telling the difference between woods that are actually much different in properties, such as IRW and walnut. I have found American Black Walnut Juglans nigra to have properties very similar to those of soft maples, such as European maple Acer pseudoplatanus, but walnut guitars are usually said to sound 'dark', while maple sounds 'bright'. I'd love to do some blind tests of that one!
IMO, the biggest physical problem with finding substitute wood is fingerboards, and that may be solvable with some sort of dying process. In terms of B&S woods, the issues are mainly cultural, I think. As such they will probably never be overcome: people will sing the praises of BRW long after the last Dalbergia nigra has been cut down and converted into a too-expensive guitar. Everything else will be grudgingly accepted although it may eventually happen that some folks will learn to appreciate it anyway.