I think it will depend largely on whether he secures the GOP nod or decides to go independent/third party. If he gets the GOP nod, it'll be important to get somebody with experience, and that doesn't alienate the neocons (going up against both the neocons and the liberals would result in a landslide against him, unfortunately, unless we change a lot of minds in the meantime). Although we clearly don't agree with their politics, it may be politically advantageous to pick someone like Jim Gilmore, John McCain, Mark Sanford, etc. A lot of the names that have come up otherwise seem like better suggestions if he got the Libertarian nomination.
Now say, for the sake of argument, that we can ignore "playing politics" (and I think Ron Paul may do this because he has clearly voiced opposition to supporting men like Rudy Giuliani in any way). Then some names that come to mind include Gary Johnson, Michael Scheuer, Craig Benson, Bob Barr, and Pat Buchanan. Please, let's avoid men without experience like Clint Eastwood, Drew Carey or John Stossel even if Paul runs as something other than a Republican in the general election (although any of them would be better than Andre Marrou, eh?)