There are four avenues available to you. You can pursue them simultaneously.

• Write to the entry clearance manager (ECM) and ask informally for a review of the decision
• Appeal the refusal
• File a new application
• Enter by train or ferry without an EEA family permit

Informal review

The UK's guidance changed a couple of years ago, but if you follow it through, it appears that (contrary to my earlier comment) the burden of proof still lies with the UK to show that there is a marriage of convenience. The EEA FP guidance linked above has two significant elements. First, it says

If you suspect that a marriage or civil partnership is one of convenience, you can request that the applicant provide evidence about their relationship or attend an interview on this basis.

...

If, following an interview, you decide that the marriage or civil partnership is one of convenience you must refuse the application, clearly setting out in the refusal letter the reasons for concluding that the marriage or civil partnership is not genuine.

First, the entry clearance officer (ECO) did not follow the guidance because (I assume) the application was refused without requesting evidence or an interview. So, for example, if the refusal said something like "I am not satisfied that your marriage is not one of convenience" then the refusal was improper. In this case you may be able to get the ECM to reverse it: It's not supposed to be sufficient for the ECO to be unsatisfied that your marriage is genuine; to refuse the EEA family permit, the ECO should be satisfied that you are in a marriage of convenience.

The other significant element of the guidance is a link to another guidance document, Direct family members of European Economic Area (EEA) nationals. This document has an extended section on marriages of convenience. This includes some additional material showing that the UK must investigate marriages of convenience. For example:

Burden of proof

An applicant must show they are the family member of an EEA national. This would usually come from a valid marriage certificate. If you suspect the marriage or civil partnership is one of convenience, it is for the Secretary of State to prove this.

The national courts must verify the existence of abuse in individual cases if there is an appeal.

Unfortunately, the factors that the guidance specifically identifies as justifying a suspicion of marriage of convenience are redacted from the public version of the guidance. So you cannot know with any certainty whether such a factor is present in your case. Older versions of the guidance named "recent" marriages as such a factor, and said categorically that marriages with evidence of cohabitation should not be suspected, but the new guidance is considerably more nuanced.

Still, the process outlined in this document requires an investigation into suspected marriages of convenience, and from your question it seems that such an investigation did not take place. An intervention with the ECM may therefore be successful.

(Unfortunately, after writing this answer, I looked for contact information for the ECM who would have been responsible for your application, and it is difficult to come by. I can't even find out where visa applications submitted in Germany are processed. The closest thing I could come up with was the general UKVI complaint channel.)

The text of your refusal letter invokes EUN2.23, which is found at EEA family permit: EUN 02. This is the old guidance, and directly contradicts the reasoning in the letter. First, the letter ignores section 2.10 (What if I suspect a marriage / civil partnership of convenience?), which says

When a marriage / civil partnership of convenience is suspected, the burden of proof is high and rests with the ECO.

Second, the letter uses the formula for cases where "the applicant does not provide any (or adequate) evidence to support his claim to be the family member of an EEA national." To evaluate whether that determination is reasonable, we look at section 2.8 (What supporting documents should family members include in their application?), which links to the supporting documents for an EEA family permit page, which says only this about evidence of relationship:

evidence of your relationship to your EEA family member, for example a marriage certificate, civil partnership certificate, birth certificate or proof that you’ve lived together for 2 years if unmarried

There's nothing about photographs, evidence of communication, or evidence of cohabitation. However, section 2.10 is the section that excludes cohabiting spouses from suspicion of marriage of convenience, so maybe you can submit just the evidence of your living arrangements. It might be wise to include a few photographs from different times for your own peace of mind.

Appeal

This requires payment of a fee, which should be awarded to you if the appeal is successful. If you are interested in the fact that the UK is flouting the law and wish to have someone say so officially, you should do this. However, the appeal probably won't be decided until several months after your planned trip.

New Application

These are free of charge. You have a couple of options here: You can submit a new application along with statements describing why the original refusal was unjustified, and how there is no basis to suspect that your marriage is one of convenience, in particular that the idea that you would have married 3.5 years before a vacation to the UK in order to be able to get a free visa is patently ludicrous. This might be successful, but it might antagonize the ECO and lead to a subsequent refusal.

The other option, of course, is to comply with the demand for additional evidence, with or without a note of protest. Since your primary goal is to go to the UK next month, this may be your best option.

Enter by train or ferry without an EEA family permit

You can also try going to the UK by train or ferry and applying for entry at the border. There have been some reports on this site of success with this approach, but it could be stressful since you won't know whether your wife will get in until she is actually in.

Advice

It's hard to say exactly what I'd do in your shoes because I have not seen the text of your refusal, but in general I would probably pursue all of these options simultaneously, or rather, start the first three at once and hold the fourth as a backup plan in case none of the first three yields fruit in time for your trip.