Next to implies an immediate vicinity; whereas near to implies "a short distance away."
In this way, you can have a next-door neighbour, who lives next to you, but your bank, a short drive away, could be near to your house.
The key to the answer, I think, is the question, "Do you think you can find it?" This would imply that it's easily found by simply looking around. Therefore, it's the "closer" of the two phrases that's being suggested. (If it was only near to, and you couldn't see it, finding it might involve having to ask for directions or looking for it on a map.)
As for near to versus just near, both can be considered correct. Although I suspect that it's more common to use just near (or nearby), adding the to is not wrong. I've heard and used both forms myself. It seems that near to is more common in the UK—and, hence, Canada where I live—than in the US. Those in the US might find that near to sounds strange.
I also found this reference to a discussion of the syntax of the "complex preposition near to."