"Between" must be used with "and." Hence,
I have a choice between Tony and Samantha.
is correct.
However, since we're referring to a choice here, "or" too makes sense. But, "and" is the best bet if you're confused about which one to choose since "and" would be correct grammatically.
Also, I think the article "a" is more suited here.
Hope I answered your question.
I recommend the following sites for great grammar info: