…ask for the “Cuban Sandwich”. Trust Me 
As a food writer who specializes in food from the Spanish Caribbean, and lives smack in the middle of a very popular tourism destination I have this to say: If you are judging the local cuisine by what you ate at an all-inclusive, you are sadly mistaken. There’s a reason why I am openly disdainful of all-inclusive tourism.
Having said that, come spend your money, even if all you want is white sand beaches, and unlimited inexpensive local booze. Pretty please. 
I couldn’t agree more, but my estimation of Caribbean food comes from living and working there–from the food that’s served in the households of friends as well as corner eateries and typical restaurants. (The saving grace of eating at the in-laws’ is that they’re half Syrian, and so the food there is actually more Middle-Eastern than Caribbean, so it’s great.) My experience in Cuba itself has not been at all-inclusives. (I’ve never stayed at an all inclusive, but have always assumed they cater to European/Canadian tastes–since those are their clients–and that the really good food in Cuba is only found in the expensive tourist places, where I haven’t been.) In La Habana I’ve eaten at familiar households and paladares, and at both I’ve been consistently unimpressed. The food at paladares can be decent; it’s just not anything to write home about. Howvever, that was almost 10 years ago, so it could have improved.
I’m curious, though: Apart from a well-prepared sanchocho or mojarra frita, which (typical-not made for tourists) food of the Spanish Caribbean would you recommend? Who can make ground provisions enticing?
Right–the issue of (lack of) flavoring in Caribbean cuisine has nothing to do with embargoes or a “struggle to get spices,” because it seems to be the same from Cuba, to Puerto Rico, to Honduras, to Colombia.
So, where should we be staying? Seriously, I’m looking for tips.
You see, this where I can’t help you. I don’t agree at all with you on this, and find the cuisine of these countries plenty flavorful. Food is a very personal experience. If you try it and don’t like it, then that’s the end of it. You aren’t wrong.
BTW, each country has its own version of sancocho. It’s like a generic name for “meaty stew”. Colombian sancocho is not like Dominican Sancocho, for example. One can like one and not the other.
I visited Cuba about 14 years ago, and I always stayed in rooms in private houses, and ate almost all of my meals in private homes.
At the time I could rent a nice room for $20 a night, and have a large lobster tail with vegetables dinner for $10.
I enjoyed many good meals in Cuba. One of my favorites was lobster spaghetti prepared by one of my Cuban friends.
Seconded! I am dying to go to Cuba as soon as I can do so legally, and I can’t afford $5 - 6k for one of the approved people-to-people trips. I speak Spanish, so I am willing to try anywhere and avoid all-inclusives like the plague.
Panama has a similar cuisine. Spanish Caribbean and Central American food is plenty tasty, even if it’s not highly spiced like Mexican or Jamaican food. It’s sort of like calling French food bland because it’s often not as strongly flavored as Italian.
There are many nice yet economical casas particulares in Havana, such as the Casa Vitrales. There are also quite a few good paladares (private restaurants).
I’ll let you know if my plans work out. I got no help asking for advice on the dope, I think it’s too US-dominated to get any useful advice here.
mrAru and I also really want to go to Cuba, though staying at an all inclusive, we still want to see some of the interesting historical locations, and some music venues [Buena Vista Social Club soundtrack really perked my interest in the music] - both of us speak a smattering of Spanish, and are reasonably adventurous [or at least as adventurous as I can be with a wheelchair.] Back in 2003 I was visiting a German friend of mine, and it was a fairly grey and rainy February. As we headed into the Real in Boblingen they had travel posters for Cuba, not counting airfare, 250E for a week per person. He wanted to fly us there until I pointed out that it would get me into serious trouble with my government … sigh
I’m guessing that the comment by Bijou Drains was offered tongue-in-cheek. Much like the statement that Mexico City is very similar to Los Angeles, except there aren’t as many Mexicans.