Chris Christie, Bob McDonnell, or Marco Rubio seem like the best choices (besides Ron Paul ) The Four Horsemen (Palin, Romney, Gingrich, and Huckabee) all have major flaws that would prevent them from winning a general election on their own merit (meaning that Obama would have to be really unpopular to lose against any of them). Christie, McDonnell, and Rubio at least seem to have somewhat of a record of reducing the size of government, which would allow them to distinguish themselves from Obama.
I don''t think Rubio would run. By the time he was elected to the Senate, other Republicans will already be making their announcements to run. I think Christie would be out too, he' just not known a whole lot by the public.