One fish that hasn’t been metioned, if you can get it where you are, is sturgeon. A firm, white fleshed fish. And I would definately second Romanperson’s comment on freshness. A good fishmonger is absolutely essential.
No I’m not being pretentious, I just really like the word fishmonger.
I wouldn’t want to mention any fish by name. Some of them are kinda sensitive about it. 
According to this thread, a list of unfishy fish:
monkfish
tuna
Wahoo/Ono
Grouper
Cod
Char
Perch
Trout
flounder
swordfish
Sole
walleye
shark
halibut
Catfish
sturgeon
I’m beginning to think that no fish taste fishy 
Make sure that when you buy fish that there is no heavy fish odor. Fish can taste “fishy”, but should never smell that way if it’s fresh. I second or third halibut as a very mild and versatile fish. Try this:
Vietnamese Halibut
Halibut filets, cut to about 1/2"-3/4" thick
Marinade:
Fish sauce
Olive oil
Lemon grass, minced
salt & pepper
Sambal oelek (Asian chili paste)
Stir fried vegetables of choice
Rice cooked with a little lemon olive oil.
Buy the best fish sauce you can find; $$=better. Marinate the filets overnight. Drain and bring to room temperature before cooking.
Stir-fry the veggies in a wok or heavy skillet, at medium-high, remove and drain. Add a couple of tablespoons of oil to the wok and flash fry the filets until just done. Do NOT overcook. They will have a slightly browned/blackened appearance. Remove from wok. Return the veggies to the wok to reheat, adding a little fish sauce. Dab a small amount of chili paste on each filet. Serve with rice.
If done right, this is a world class dish.
Chicken!!!
Please, please, please try this one if you haven’t.
Use Swordfish or Halibut steaks, Swordfish is better, whether fresh (best) or frozen (some states don’t allow fresh shipments).
If you can grill them, all the better, but being it’s February…
Use a cast-iron skillet. Nothing else, try to use one with the “ribs”.
Set the heat to 8 out of 10 (whether gas or electric) and melt enough butter to reach close to the top of the ribs. Let the pan get HOT!
Aside: the ribs give the seared look to a grilled steak, using a flat-pan is just as good, as long as it’s cast-iron. It’s the only pan-type that can take the heat needed. Adjust butter to type.
Keep in mind, get it HOT, to where the butter is just smoking. Put the steaks in and cook for 5 minutes, turn for another five minutes, cut the side with the skin off and serve.
Bonus: season each side before opposite cooking with some salt and pepper.
X-tra bonus, clarified butter. Melt about 3 TBS per serving over low heat. When melted, use a spoon to skim the white stuff off the surface. You’ll notice solids at the bottom, drain the butter off into a small bowl without letting the solids in. Dump the remains, wipe with paper towel, and return the bowl contents to pan. This should be done before cooking fish.
Using clarified butter, a slice or two of lemon wedge, and swordfish/halibut, there is no reason to screw it up with fancy marinades. My wife hates shellfish and most seafood, but she lives for this since I got her to try it.
BTW, the butter is for dipping the bites. 
Lemme know how it goes if you try it.
My mother has the same aversion to fish; however, living in Florida, she had to come up with one dependable fishie to eat. Her solution: Grouper.
Best of luck, Robert
I’ve had monkfish only once. I was surprised at the first bite; to me, it tasted just like lobster. I would have eaten it on other occasions, but lunches at this particular restaurant could start getting expensive.
Try salmon with Soy Vay Veri Veri Teriyaki sauce. Score the fillet so that the sauce gets well into the flesh. Put the fillet in foil and pour on the sauce. Bake in the oven as usual, or gook it on the BBQ grill. Your mouth will have an orgasm.
“cook”, not “gook”. :smack:
Is it possible to get Catfish other than in the south? I know there are huge ponds that are basically catfish farms in the south, but I don’t know if it ever gets sent outside of the state. The taste is very good, and much better if you don’t fry it. I am sure there are plenty of good recipies.
My mom managed to tap into a network of Japanese-Americans in her suburban US community who get fish from suppliers that distribute to the better local sushi joints. A sushi bar’s fish distributor is an important factors in whether the sushi’s any good (chef’s up there too). Freshness is essential for sushi, and though it’s kind of a waste (to me) to cook sushi-quality salmon and tuna, it is definitely better (“less fishy”) when cooked than some stuff you buy at grocery stores (unless your grocery store happens to make good sushi). Buddy up to your favorite sushi chef, or ask your Japanese-American friends if you don’t dig on the raw stuff.
I also like the idea of eating fish, but I don’t like fishy-tasting fish. I’ve found that basa has virtually no fish-flavour at all - I made a nice oriental rub (soya sauce, lemon juice, garlic, salt and fresh ground pepper), rubbed it on the fillets after buttering them, wrapped them in tinfoil and poached them on the barbecue for about half an hour. Best fish I’ve ever had, and no fishy flavour at all. Basa does seem to have a very soft texture though, so you need to be careful how you prepare it. When I tried poaching it in water and orange slices, it came out almost mushy.
I’m really picky (unfortunately) about food, and that extends to fish. I’m like your wife, in that I don’t like salmon at all, unless it’s prepared a certain way. I like kippered which is similar to just plain smoked. It’s almost blasphemous for me to say so though, being from the Pacific Northwest.
I liked a lot of the suggestions in this thread, particularly the ones about rinsing or soaking fish really well, and whitefish. I’ll also add I’ve never found orange roughy to be too fishy.
I’m not as bad but I’m in the same boat. I think that a lot of fish tastes too “fishy”.
What’s worked for me-getting freshwater or warm saltwater fishes. Tuna and salmon and so on are oiler and have more a “fishy” taste. In much of the US, its possible to get really fresh catfish(which is the same as basa I believe) and I like that a lot. Another suggestion is to soak the fish in either a mix of lemon juice (or vinegar) and water or in milk for a bit, drain it and then proceed. That soak in milk really helps remove a lot of the “fishy” flavor.
Hope that helps.
This thread inspired me to have monkfish for dinner. It was bloody good. Is it really endangered? – a huge fresh fillet cost me $5 Canadian.
From a Norwegian site:
From Maryland Department of Natural Resources:
From a personal website:
Incidentally, from the last site:
So it looks as if the monkfish population is not endangered; however, populations have dropped in some regions due to overfishing. (I believe the same could be said for swordfish.)
And it does taste like lobster.
Holy Crap ona stick!
This far down the thread and not a single mention of…
Marlin
I’m not a big seafood eater. I don’t like much fish, although I can deal with fresh caught Walleye or Bass (being in Minnesota).
But Marlin, with a little pepper, lemon pepper or even a small dab of butter. Grilled for 5 minutes on a side.
Yum.
Reminds me that I have some in the kitchen right now…
The most un fishy fish I can think of is shark. Probably becasue it isn’t a fish.
I was on a fishing boat once where they landed a 12 foot thresher shark. Cut its head off, and cleaned it right on the deck. They cut it into steaks about 1.25" thick. The cook grabed several put them into foil with lemon, onion, salt peper and a little butter. wrapped them up and tossed them on the grill. Twenty minutes later was the best fish I have ever eaten.
Okay Rick I’ll bite 
Sharks aren’t fish because?
I’m aware that there are a number of differences between sharks and “regular” or “true” bony fish. AFAIK they are still taxanomically classified as fish. Members of a subclass that includes rays, skates and chimaerras correct?
Webster defines: Shark
Any of numerous chiefly marine carnivorous fishes of the class Chondrichthyes (subclass Elasmobranchii), which are sometimes large and voracious and have a streamlined torpedolike body, five to seven gill openings on each side of the head, a large oil-filled liver, a cartilaginous skeleton, and tough skin covered with small toothlike scales
http://en.wikipedia.org/wiki/Shark and wikipedia claims they are fish also.
or have I been whooshed…again. Now tell me this is a Dubya quote that I missed.
As an on-again off-again vegetarian (for health and picky-eater reasons only), I wouldn’t worry so much about what kind of fish. In fact, pick one kind and stay with it and others similar to it, and try preparations that really hide the true flavor of the fish. Seafood afficianados will cringe, but she won’t get use to fish until she eats it frequently. Try a recipe that completely smothers it in sauce, and keep trying more recipes that let more of the fish flavor stand out a little bit at a time.