Defining the issues
Definitely I can say I'm better than him
Here's at least part of the issue. I get the impression that you think that the team leader should be the person who's best at all the tasks you're doing. This isn't necessarily the case - IMO, the team leader should be the person who's best at leading the team to do all the tasks that need doing.
In other words, the team leader should be the one who can keep track of what needs doing, prioritize among the jobs, know which member of the team is best suited to do any particular job, is able to get that person to actually do the task (even if/when they may prefer to do something else), know what's getting done and not, and make sure that the manager/clients get the feedback they need.
You also wrote that
I'm messier than him.
That's something that he may see as an indication that you're not going to be structured in your work and thus he doesn't trust you to do the job according to the procedures and standards that are current in your company.
Also, it's a fair bet that he's picked up on your view of him - that he's less competent than you and that he's treating you unfairly because he knows you're "better than him". These things are likely to give him a view that you can't be trusted to do the job properly according to his/company standards, and that you're likely to try to show him up in front of both your superiors. Given this, why should he trust you?
You need to win his trust.
Stop thinking you're better than him. You are certainly better at some things, but you're not better at all things. Not even all things needed for your job. Also, he's been there longer than you - this means that he knows more about the company than you do. You may be the best network engineer to ever walk the earth, but he's the one who knows what this company needs. That's more important than most of us like to credit.
Second: You're messy - work on that.
Use GTD, or Time Management for Systems Administrators, or whatever system works for you to keep some structure both on your time and your desk. Schedule time to do the boring parts of your job - documentation, feedback, managing emails... Show him that you are actively working to improve your behavior and to be a better coworker.
Third: Talk to him.
Ask him what he thinks you're doing well, what he wishes you would do different, and find suggestions on how to improve. Then follow through on that.
Ask him what bugs him the most about the systems you work with. Come up with suggestions about how to improve that issue. Don't ever use the words "But why haven't you done $THING..." - that implies that he's stupid for not having done $THING, and will make him go on the defensive to tell you why $THING is impossible. Instead, make it a suggestion - "I've not been here as long as you, so I may be missing something here, but do you think that if we do $THING it might improve the $FOO issue?"
Once you actually talk to a person, treat them with respect, and show that you're working on improving the areas where you're not currently doing well, it's amazing how much the relationship can improve and how much more fun the job becomes.