The potato is probably not as important as the method. Simply frying them will not get you the fry you want. Basically you boil them, then double fry them. Here are the steps for The Perfect French Fry:
Ingredients
2 pounds russet potatoes (about 4 large), peeled and cut into
1/4-inch by 1/4-inch fries (keep
potatoes stored in a bowl of water)
2 tablespoons distilled white vinegar
Kosher salt
2 quarts peanut oil
Procedure
Place potatoes and vinegar in saucepan and add 2 quarts of water and
2 tablespoons of salt. Bring to a boil
over high heat. Boil for 10 minutes.
Potatoes should be fully tender, but
not falling apart. Drain and spread on
paper towel-lined rimmed baking sheet.
Allow to dry for five minutes.
Meanwhile, heat oil in 5-quart Dutch oven or large wok over high heat
to 400°F. Add 1/3 of fries to oil (oil
temperature should drop to around
360°F). Cook for 50 seconds, agitating
occasionally with wire mesh spider,
then remove to second paper-towel
lined rimmed baking sheet. Repeat with
remaining potatoes (working in two
more batches), allowing oil to return
to 400°F after each addition. Allow
potatoes to cool to room temperature,
about 30 minutes. Continue with step
3, or for best results, freeze
potatoes at least over night, or up to
2 months.
Return oil to 400°F over high heat. Fry half of potatoes until crisp and
light golden brown, about 3 1/2
minutes, adjusting heat to maintain at
around 360°F. Drain in a bowl lined
with paper towels and season
immediately with kosher salt. Cooked
fries can be kept hot and crisp on a
wire rack set on a sheet tray in a
200°F oven while second batch is
cooked. Serve immediately.
Worth reading is also the science behind the perfect fries.