First I would try one of
these.I have seen this before. I ran 15k air conditioners for years on three different fivers with a Honda Eu3000is, but I've seen others tailgating with the same generator and a 13.5k unit that just wouldn't start. One fellow, in particular, went so far as to replace the ac with a high efficiency unit and never had another problem.
One last thought: I would not hesitate to parallel one of these capacitors with whatever may be present under the housing cover. Paralleling capacitors (different from resistors) results in adding capacitance, which can only help.