Use an installer, sign your executable, and sign your installer! The user needs to know who you are if they are going to let your program spy on their traffic.
Yeah I was just looking into this this morning - who do you recommend I use for code signing?
We use GlobalSign and I have no complaints. But that's not really a recommendation -- there may be cheaper options available.