Tiger shrimp. A great bit of information on them here. Actually this site has LOADS of shrimp information. http://www.planetinverts.com/Tiger%20Shrimp.html
Tiger shrimp are a different species than red cherries, but very similar. They are more expensive than RCS so I would be hesitant at providing a very expensive snack for your betta.
As for sexing. For cherries (neocardinia, cardinia, and ghosts, it is very easy).
Females are larger and brighter, and have a curved under belly. (Opposite of most of the rest of the animal kingdoms!). Also females have an obvious saddle, this is eggs ready to be fertilized. Either yellow of green, it's on their back. For real obvious indicators, a belly full of eggs is the ultimate give away.
This is my own tank. The two dark red shrimp are females, the lighter, paler one is a male. And the smaller squiggles are frenzied feeding young shrimp.
For clearer pictures, read this page. It also includes clear shots of babies, how to sex, the saddle, and even the male "appendage". Plus shots of them in the act. http://www.planetinverts.com/shrimp_reproduction.html
As for how many, well that all depends on the species, are there live plants, water paramaters, etc. And hiding spots. You could start with a trio of RCS, two female, one male. This is the ideal way to start. You might end up with a few babies out of it. IF there are any left overs they will scavange. IF there is any driftwood they will clean it, if there is any leaf litter they will munch it.
2 amano would also be a good place to start.