You should use Russet potatoes. They are the best for frying because they are dense and high in starch and low in moisture. These dense potatoes are perfect for frying because of the starch they brown perfectly on the outside, and the dense center makes these potato bites a delight to eat.