You should get rid of Bill, if it's in your power to do so on your own decision, or look for another position for yourself if you can't.

Bill sounds not so much as the 10x employee, like some comments here say, but more like Wally (from the comics strip Dilbert): someone who's good at making a lot of fuss; making it look like he's a model employee, while in actuality, being lazy; bad for team spirits; disrespectful; doing work that he shouldn't be doing instead of the work he needs to do and, to top it off, being a good enough actor that he made the "pointy-haired boss" believe he is better at your job then you are, so musch so that the CEO said what you quoted him saying to Bill while your in the same room.

Actually, in light of that last point, you should start by looking for a new position for yourself, and only if that doesn't pan out, "take care" of Bill.
Your CEO sounds exactly like the guy to be impressed by false bravado of Bill/Wally types.

If you want to "take care" of Bill, others have told you how exactly so I won't repeat.

I would add that another tool, aside from (electronic) paper-trail is the insinuated threat of dismissal (assuming, as I stated before, you have that power by yourself, at your discression).

Some other commenter here said you really should "earn" Bill's respect... I disagree.
While true, you're not in the armed forces, where rank is the beginning and end of all arguments, you are his superior.
Having his respect would be nice, it would show he understands and values what you must have done and acheived to get to where you are today: being his boss.
But it's not mandatory!

I have had the misfortune of working for people I didn't respect or appreciate.
I did my job, did only my job, and did my job to the best of my abilities.
Wanna know why? Not because I respected my superiors and thougt they knew better than me because they had more information and abilities than I have. Oh no.
I did it because I needed the job and it was in their sole power to dismiss me had I not done my job, on the best side, not being a Bill/Wally.

In a perfect world, it is Bill, not you, who should look out for a place where he can respect his superior, feeling he's being utilized correctly.
I suspect such a place never will exist since Bill probably also has a very high opionio of himself (hence his talking back, disrespect and going over your head... he's superman, capable of running the entire company alone.. when he's not slacking and doing anything other than his job that it).

But we're not living in a perfect world, you not only not have your boss's support, it sounds your boss disrespects you as well and your very own Wally made it a point of becoming you (probably he thinks in your position he can do even less actual work, while blaming subordinates for slacking, and have better leverage for his next conquest).

Get out, now, and let the CEO find out exactly how much can Bill actually get done, once your "lazy ass" will be gone.

You should get rid of Bill, if it's in your power to do so on your own decision, or look for another position for yourself if you can't.

Bill sounds not so much as the 10x employee, like some comments here say, but more like Wally (from the comics strip Dilbert): someone who's good at making a lot of fuss; making it look like he's a model employee, while in actuality, being lazy; bad for team spirits; disrespectful; doing work that he shouldn't be doing instead of the work he needs to do and, to top it off, being a good enough actor that he made the "pointy-haired boss" believe he is better at your job then you are, so musch so that the CEO said what you quoted him saying to Bill while your in the same room.

Actually, in light of that last point (and after going around this thread reading your comments about your relationship with the CEO), you should start by looking for a new position for yourself, and only if that doesn't pan out, "take care" of Bill.
Your CEO sounds exactly like the guy to be impressed by false bravado of Bill/Wally types.

If you want to "take care" of Bill, others have told you how exactly so I won't repeat.

I would add that another tool, aside from (electronic) paper-trail is the insinuated threat of dismissal (assuming, as I stated before, you have that power by yourself, at your discression).

Some other commenter here said you really should "earn" Bill's respect... I disagree.
While true, you're not in the armed forces, where rank is the beginning and end of all arguments, you are his superior.
Having his respect would be nice, it would show he understands and values what you must have done and acheived to get to where you are today: being his boss.
But it's not mandatory!

I have had the misfortune of working for people I didn't respect or appreciate.
I did my job, did only my job, and did my job to the best of my abilities.
Wanna know why? Not because I respected my superiors and thougt they knew better than me because they had more information and abilities than I have. Oh no.
I did it because I needed the job and it was in their sole power to dismiss me had I not done my job, on the best side, not being a Bill/Wally.

In a perfect world, it is Bill, not you, who should look out for a place where he can respect his superior, feeling he's being utilized correctly.
I suspect such a place never will exist since Bill probably also has a very high opionio of himself (hence his talking back, disrespect and going over your head... he's superman, capable of running the entire company alone.. when he's not slacking and doing anything other than his job that it).

But we're not living in a perfect world, you not only not have your boss's support, it sounds your boss disrespects you as well and your very own Wally made it a point of becoming you (probably he thinks in your position he can do even less actual work, while blaming subordinates for slacking, and have better leverage for his next conquest).

Get out, now, and let the CEO find out exactly how much can Bill actually get done, once your "lazy ass" will be gone.