Animelover:
The idea of eating something raw is far worse than the reality. Good fresh sushi and sashimi is better than the most tender fillet mignon. When raw fish is fresh it has no "fishy" taste at all, iin fact its delicate and melts in your mouth. When I was 5 my mom took me to a japanese restaurant. She ordered sashimi - which is small squares of raw fish with no rice or seaweed- and as any 5 year old would I teased her "eewww! how can you eat RAW fish!?!?! That's disgusting!!!". Good old mom challenged me "How do you know its yucky unless you've tried it?" and offered me a pink, glossy slab of raw salmon to try. Determined to prove that it was yucky, I ate it and was shocked to find that it was the most delicious thing I'd ever eaten. Instead of spitting it out and saying "eeew!!!" I asked my mom for another piece!!!
I'd also like to point out that all raw fish in the united states is flash frozen to kill any potential parasites. You don't have to worry about getting sick, unless the sushi is stale- you'd be able to tell by the smell, if smells like canned tuna its stale.
Good fresh fish should have the pleasant scent of the ocean.
Sadly I don't know of any places in Albany, but if you ever take the train down to NYC I can recommend a few places. If a restaurant is out of the question due to budget, there's a japanese grocery store in NYC called Sunrise Mart. You can find all sorts of food as well as mochi!! There's also a place that sells yakisoba and takoyaki, which are gooey fried dough and cheese balls with a piece of octopus inside- it's soooo good!!!
I love cha-soba, its soba buckwheat noodles flavored with green tea, its sometimes served cold with a dippping sauce. You can't go wrong with tempura, batter fried shrimp and veggies. If you like tofu, a very good inexpensive appetizer is "agedashi tofu", its deep fried tofu cubes in a very nice dipping broth with fresh grated ginger and daikon (japanese radish). Broild eel is very good, I forgot the japanese name for it, but its another tasty treat that doesn't taste fishy at all. Japanese food will give you a fondness for seafood like never before.
If you are open minded enough to try sushi/sashimi, I'd start out with salmon, hamachi (yellowtail tuna) and toro (tuna). Those are the basics and most novice friendly. Once you've adjusted your palette, you can move on to other things. Also, if you have the chance to try monkfish liver, try it!! It tastes like lobster!!