"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:

http://englishisducksoup.com

http://www.queens-english-society.com