As you say, corvids, octopi and others have recently been interacted with in such a way as to be shown to demonstrate unexpectedly complex behaviour. Brain size doesn't seem to be quite as important as you might think.
Note my brain is about a fifth the size of a blue whale's brain. Now I am absolutely useless at living within the sea and I have no idea how complicated it is but I suspect that based on our relative brain size, that it can be very complicated compared to what we land lubbers get up to. Evolution doesn't leave rubbish lying around unless it does not impair things.