"Between" must be used with "and." Hence, 

*I have a choice between Tony and Samantha.*

is correct.

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