1. Blue Velvet and Fire Reds are both Neocaridinas so they breed together and produce brown/wild-type offspring.
2. There are OEBT (Orange Eyed Blue Tigers) that are a bit cheaper. Royal Blue Tigers are a bit more expensive, but breed more true and usually are a nicer shade of blue. There are Black Eye (Regular) Blue Tigers, though I don't often see them anymore since Orange Eyes are much more preferred. You could get culls of OEBT that don't have the best blue coloration/coverage, but they are likely to produce offspring with not as nice blue as well. There are blondes of OEBT, but those are lowest grade with very little to no blue.
3. Tiger Caridinas most often work out being kept with Neocaridinas. Tangerine Tigers are inexpensive and very hardy. Nice color and breed true. Other tiger options include, Black Tigers (BTOE), Red Tigers, Super Tigers etc.
Sulawesi shrimp (Caridina) like high pH, but are pretty sensitive and require their water parameters to be specific.
Most other Caridinas (Crystals, Blue Bolts, etc) like much more acidic soft water than Neocaridinas and Tigers. Tigers do like water parameters closer to Neocaridinas than the other Caridinas, which is why they are usually more compatible.
Ghost shrimp, Amano shrimp, Bamboo/Flower/Singapore Shrimp, Vampire/Viper/Giant Blue Wood Shrimp are usually other compatible options, though don't expect them to breed (ghost can though).
It still does depend on your water parameters though (pH, Temperature, KH, GH, TDS)
Take a look here to see what shrimp are even able to survive in your water. Neocaridinas are hardy and can adapt to a wide range of parameters.
Dwarf Shrimp Water Parameters ? DiscoBee
If you don't have test kits, I do recommend getting some (pH, KH/GH especially. TDS if going for sensitive species)
If the Fire Reds are pretty new, I would wait a few weeks to see how the shrimp do in that time frame, just to make sure they really do well in your water or not. It will give you more experience as well before stepping up to another shrimp.
When doing water changes, it seems shrimp prefer smaller water changes (10-20%, can do more frequently) rather than large ones.