Ghost Shrimp are a great choice, because they're inexpensive. Shrimp will generally require some sort of hardness in the water, because they need to form new shells when they molt. My water is generally hard so I've run into no problems. You may want to test your water hardness before getting some.
Make sure you aren't dosing with chemicals that may contain heavy metals, like copper. Invertebrates don't do well with copper.
Red Cherry Shrimp may be another option for you. They're a bit more colorful and just as hardy as Ghost Shrimp in my experience.
No matter what kind of shrimp you choose, make sure they have hiding places. Nooks and crannies in rocks, Java Moss, or ornaments are good to have. Any fish will try to eat shrimp that will fit into their mouths. The fish you described should pose little problem to the shrimp I mentioned even when they are half grown. Baby shrimp might be a different story, but I've personally never seen them. I just see juveniles show up randomly, so some of the eggs must be surviving.