On Earth humanity has taken the dominant role (excluding dolphins and mice of course). We know of conflicts in pre-history where our ancestors have overtaken other species and slowly wiped them out.
What circumstances would allow two (or more) species to evolve on a planet side by side? What could have happened differently to allow Neanderthal man and our ancestors to survive and thrive to the present day?
There are a lot of different factors that could apply here, and in most cases it could well be a combination of factors that come together to give this result.
Here are a selection of possible reasons though:
Geography
The two cultures evolve on different continents. Sea travel has not advanced to the point that either is capable of invading the other but they do have some contact (for example occasional adventurers, shipwreck victims, or trading vessels may cross the sea).
Morality
One is stronger than the other but has developed a "modern" moral standpoint where they do not attack the weaker species.
Habitat incompatibility
The two species live in very different areas. For example one is aquatic, one land based. Or one is adapted for cold climate and the other for hot.
There would be areas where they meet and trade but the main drivers of conflict wouldn't apply as they use different resources.
MAD
The two species have managed to hold on and develop to the point where both have atomic weapons and a tense stand-off has developed.
Religion
One worships the other as gods/saints/deities/etc.
Positive Inter-dependency
The two species are somehow biologically important to each other, for example there is a stage in the life-cycle of one where it is dependent on another and both species benefit from the arrangement.
Parasitism
One could even be a parasite on the other, for example sentient cuckoos/changelings that exist hidden within the host's society and use it to raise their young.
Slavery
The classic case would be a stronger but less bright species and a more intelligent species. Any other unique ability such as flight could also lead to the same situation though.
One species enslaves the other and uses them to provide the ability they don't have.
There are several parts which must be considered which (i have to speculate) would promote the evolution of two (or more) sentient, reasonably intellegent, native species in a single environment (planet but the same arguements could work for localized regions, exotic environments, or collections of planets).
Intellegence has, most likely, only evolved once on planet earth since it came into existance. We have never found another species with advanced intellegence. I, therefore, infer that the probability of an intellegent species evolving independantly at any given time is low. If there are two specied evolving in parellel, however, this must happen.
Pure Chance While low, there is a finite chance that a planet where intellent species can evolve in two indepentent environments, two or more will evolve independently around the same time. I would expect that if this were to happen, they would be at vastly different social and technological levels when first contact is made.
Common Cause A species evolves to fill a niche. If that niche which requires intellegence forms around the same time such that two species attempt to fill it, it is possible they would both become more intellegent while striving for the same goal. This would lead to competition increasing the chance for one species to die, but more on that later. While one would expect simular creatures (common ancestors) to fit the niche well, they could feasibly be vastly different.
Interspecies Interactions Promoting Evolution Two intellent species could feasibly form if the existance of one promotes the evolution of the other. War, for example, has advanced humanity more than I think we would like to admit. Both species could evolve with regard to intellectual capacity in response to competition (violent or otherwise) between them. Evolution of defensive and offensive characteristics evolve in response to other species. As long as one doesn't kill of the other, they may advance the species that way. They could also peacefully promote intellectual growth. In billions of years, one could speculate that mice could evolve to be significantly more intellent in order to make use of our refuse or dogs/cats in order to keep us happy. By the time they reached a level of sapience, we would likely recognize the change and promote it as long as we saw it as cute/valuable/non-threatening. Those are, of course, far from the only possible examples.
Divergence Finally, two species are very likely to form intellegence at the same time if they separate into two groups and then continue to evolve. This is why we actually do see different races and did see Neanderthals. If two groups become isolated either by physical separation (distance, different living conditions, etc) or just refuse to reproductively interact (due to disease, classes, social stigma, etc), exchange of genes between the groups will cease and, eventually, could lead to the formation of two different species. The reasons why they may separate could be the same ones that cause them not to interbreed into one species again.
There aren't any Neanderthals anymore. They no longer exist for two reasons: We killed them and took their niches and we sleep with them until they were now part of us. If one species kills off them other completely, of course they cannot both become dominant species on a single planet as one will be dead. If one incompassionately outcompetes the other in every area, the other will die off as he will have no niche in which to survive. Finally, if all members interbreed regularity, the results after millions of years will be just one species with a broader gene pool. I think that is how I would want to go.
Basically, you would find yourself trying to come up with a reason they would not interbreed and would not kill each other.
Environmental Separation The most common, likely, is physical separation. If both species live in different environments (geographical, one is in trees the other in oceans, etc). This would prevent war and breeding. The other answer covers that significantly.
Social Separation While it is hard to believe it could exist for millions of years the same, if there is some reason on group will not interact (love or hate) with the other despite being in the same locality. This could be classism (one is a slave/subordinant race), pacts (stay away from me and I will stay away from you), or unamorous non-violent relationships (do you really want to sleep with an ogre or ewok?)
Incompetitive Incompatibile Biological Differences Even if you would breed with an ogre could you? Their biology is likely completely different and will likely not result in children. Likely the biology of one species may not promote violent competeition or violence. I won't kill you if you spray me with poison as you die. I will not need to kill you even if I am starving if I can't eat you or chokeberries and you only each chokeberries.
Economicish Variables Finally, this can mostly be described as a cost benefite anaylsis over millions of years and (potentially) billions of players. If there is never a reason or benefit for either species to kill or breed with each other, they won't (on a species ending genocidal scale). If mermaids trade us sushi for grass but look like blobfish I don't think we would kill or breed them out of existance intentionally. We may, however, cause war by accidental/inconsiderent pollution.
The real barrier to having two sentient species at the same time, especially two with the same mental capacity, is deep time.
Deep Time is a concept of Stephen J. Goulds wherein he notes that studying paleontology gives one a sense of time as a vast space in which we occupy just a tiny fraction.
Multicellular life evolved 1 billion years ago. Mammals and birds supplanted Dinosaurs 65 million years ago or 6.5% of total time of multicellular life. The genus Homo Sapiens first appeared 4 million years ago or 0.4% of the span of multicellular life. Actually Homo Sapiens Sapiens (modern humans) evolved just 100,000 years ago at most or 0.01% of the total span.
What are the odds that two wholly related species would evolve in parallel on the same planet at the same time? Even if they were just 1% off from each other in time, they would miss the other entirely.
The best scenario would be to have separate but related species springing from common semi-sentient ancestor. They were geographically isolated, preferably in significantly different environments and therefore developed into separate distinct species.
Interesting question, with thought provoking answers. Both Kain and Tim B provide some good pointers for world building.
I would just like to add that as far as humans go, over the last one million years we have had more than one species of humans walking the planet.
Props to TechZed's answer regarding deep time. Two truly different intelligent species would need a good back story. But that's part of the fun :)
The species must be different enough to take the ecological niches so non overlapping that they would not compete significantly with each other. For instance, they must be adapted to the climate conditions so different, that area occupied by another species would not look more attractive than Antarctica for us.
Species with similar niches do not co exist. One is always slightly stronger and pushes another out. This is true for all species, so should be true for thinking species as well. The only exception is if the environment has some stable variations, say humans would be stronger in summer and neanderthals in winter (probably was not the case).
Geographical separation may work for some time, but as civilization evolves it soon takes over the whole planet even with rather primitive means of transportation.
