Actually, squids are downright stupid. Octopi are the smart ones.
And it is most certainly possible to have sentience without fire. Unless you gauge "sentience" solely by the usage of fire. It was important for humans, because it allowed us to spread into colder climes more easily, and eat more kinds of food. Sea animals wouldn't really have that problem, since the temperature of the ocean doesn't vary so much as it does on land, and they're perfectly adapted to eat what they do eat as it is (humans weren't, because our digestive systems, etc. had to support a whole range of foods, meaning none of them would be done particularly well. Octopi eat fish, simple as that, and one fish is about as good as another). Usage of simple tools would be more important.
However, it is kinda hard to see sentience coming from sea animals. For one thing, it's absolutely unnecessary- life is goodfor all when you're underwater, there's plenty of whatever you need, or there's a depletion and nothing in the world will save you. All you need to do is avoid those who would eat you, and that doesn't really require intelligence so much as (in the octopus's case) one of the best stealth systems in the world, and good senses.
If anything else becomes sentient (and no doubt something will, at some point), it'll be on land, and in fairly harsh conditions. Not too harsh, since then they won't be able to support the extra energy consumption and birth times associated, but bad enough that the animal needs to evolve to make life easier for itself. And both predation and environmental problems have to be present.
