It isn't actually clear whether intelligence is anything other than some emergent phenomenon of suitable connected 'simple heuristics' and 'learning algorithms'. If you as me, we also are overglorified Eliza's.
There is one big difference: we can reason about reason (meta reason), Eliza can't.
It is not a difference in degree, it is a difference in kind and seems to be unique to higher primates (you can learn a dog to do tricks, but it won't spend its time coming up with new tricks), one of the most interesting science videos I have ever seen is one where a bonobo learns to write a symbol that had been on a computer it used to express its emotions.
Your statement about dogs is untrue. Dogs, and a lot of other animals, have the ability to think creatively, i.e. to come up with new stuff, new tricks. A lot of animals also have self-awareness* (e.g. dolphins, elephants, magpies). Of course, we as humans excel at the task of thinking, since it's one of our greatest advantages, but the task of thinking and being self-aware is found in other animals, so there must be a way of reproducing this.
What spawns creative thinking and self-awareness is of course a mystery, but I think it's a consequence of creating a complex enough system and creating a system that's built on ordered chaos.
We like to think we can reason about reason, but to some extent we are simply regurgitating prior knowledge, or trying some random combination of old concepts and getting lucky. If this were not the case, we wouldn't have had to wait until the 1900s for Godel's theorem -- we would each discover it independently during childhood. Godel was standing on the shoulders of giants, just as we are when we use his work, or set theory, or mathematical notation, or rules of logic, or language. In a way, our intelligence is the byproduct of a stochastic program that has been running for thousands of years consuming billions of terabytes of memory. It seems rather cruel to expect Eliza to match us under her more limited conditions.
And it is a difference in degree. A dog frequently comes up with new, previously unseen behavior -- burying certain objects, shredding toilet paper, etc. The problem is that most behaviors are not seen as useful by humans, hence they go unrewarded as "tricks". But there are also examples of dogs learning useful behavior on their own, from learning to bark something that sounds like "I love you", to learning to knock down an owner who is about to have a seizure, to learning to fetch the leash when it wants a walk.
Defining "intelligence" as "doing something that humans can do that animals and computers can't" seems somewhat self-centered (although I admittedly cannot think of a better one off the top of my head).
That difference in kind is probably an illusion created by the magnitude of the difference in degree.
From what I've gathered, the consensus, both in neuroscience and in philosophy of the mind, is that consciousness is totally emergent from the "simple" building blocks; there's no specific component unique to higher primates that explains the difference.
