I'm wondering whether I should also block hosts that don't have a valid RDNS matching the EHLO?
No, you shouldn't. Blocks a whole email only by one criteria it's a bad practice.
If I do this, am I going to make trouble for much legitimate mail and upset my customers?
more likely you do and will lost legitimate mail
I'm also wondering if I can compromise by checking that RDNS is at least set to something, but not try to match it to the EHLO. Is this possible with Postfix (and is it useful)?
yes, it possible. You can use reject_unknown_reverse_client_hostname instead of reject_unknown_client_hostname
Unfortunately, postfix doesn't have a flexible options for "complex decision". In exim you can add some points for such mails, for e.g.
Score = 0
1. The HELO or EHLO hostname is not in fully-qualified domain or address literal form. Score +=10
2. The HELO or EHLO hostname has no DNS A or MX record. Score +=20
3. The HELO or EHLO hostname is listed with the A record "d.d.d.d" under rbl_domain. Score +=20
4. The sender domain has no DNS A or MX record. Score +=10
5. SPF checks return softfail. Score +=10, fail, Score +=20
And so on. After all checks will be completed and if you had Score > 100, you can reject mail. Actually you can get such behavior, but you would need to write your own policy service