The most significant similarity that Gatsby and Nick portray is their quest that includes great expectations. Nick looks forward to being a successful 'bond' man. Gatsby looks forward to having a successful relationship with the woman of his desire. We don't necessarily hear Nick's full story, but are never given the idea that he has any great success. Likewise, Gatsby does earn his girl, but not fully, and everything eventually dies.
They differ by their approaches to reality. When it is time to give up on Daisy because she is obviously back with Tom, Gatsby won't do it. When a murder is committed, Gatsby cares nothing for the loss of life, but cares completely for how loss of life affects Daisy's psyche.
Nick doesn't approach life this way at all. If you look at the first couple of pages of the book, Fitzgerald goes out of his way to develop the reliability of the narrator. This causes the reader to trust Nick because he's truthful, not swayed by anything, and he doesn't judge. Nick has a very realistic view of his situation.
Hope that gives you some additional insight.
The most blatant way that they are paradoxical is honesty. Gatsby's entire life is a lie. Having left the name Gatz behind, he's created a new persona. Nick, on the other hand, is the picture of honesty.
"Every one suspects himself of at least one of the cardinal virtures, and this is mine: I am one of the few honest people that I have ever known." (56)
They are similar in that they both came from rural beginnings. Gatsby's (Gatz') parents were farmers and Nick comes from the midwest. And despite Gatsby's outright lying, Nick finds him to be more redeeming than any of the other shallow characters in the novel. Nick looks on him with more sympathy and an open mind. I always thought this quote set that up:
"In consequence, I'm inclined to reserve all judgments, a habit that has opened up many curious natures to me and also made me the victim of not a few veteran bores" (7).
Perhaps, this is because Nick sees Gatsby as a dreamer and that Gatsby puts up with his lifestyle and his shallow circle of friends, not because he is shallow himself, but as a means to an end: which is to win Daisy back. Nick is guided by moral principles and Gatsby is guided by a dream. The other characters seemed to be guided by not much more than parties, social standing and gratification; Gatsby and Nick have purpose.