I had always been taught that fish and seafood were excluded, perhaps the Orthodox differ on this. Although, I believe crustaceans (lobster, shrimp, crab) are considered scavengers and prohibited under strict kosher law, so I don't know how (if at all) that may have figured into tradition.
it was not always taught that fish were excluded, if you read back it started as vertebrates and was generalized to seafood...
We can eat any type of "fish" or shellfish without a backbone. That means clams, oysters, mussels, squid, octopus,shrimp, cuttlefish etc. What the old timers taught was that one had to abstain from anything which had blood in it or came from something with blood in it. Because they didn't see any red blood in invertebrate sea food, it was OK. Most fast days in Great Lent we also abstain from wine and olive oil.
The only variation on the fasting rules that I am aware of is with the Cypriots who say that chicken isn't "meat". Honestly, they do. Go figure.
MT, go easy the first year; work into the fast. Your experience about the meat being easy and the dairy/eggs hard is right on the money. That's pretty much what we all find and think how hard it is to find things to eat which don't have either milk or dairy products or eggs of some sort in them.