That’s true. AFAIK, any deterministic function of publicly revealed data (e.g. size, num outputs) should work. One can even include blockchain data outside the transaction, e.g., how full were the past N blocks. (Note that this does not alter privacy re: eclipse attacks because shielded transactions already choose the Merkle tree anchor depending on public on-chain data.)
How about a concrete soft-fork proposal:
min_fee = 0.00001 + 0.00001 * max(0, #nullifiers + #shielded outputs - 3)
That is, the fee is fixed 0.00001 ZEC per transaction plus additional 0.00001 per each shielded input/output with first three being free. Thus, this proposal changes nothing for the common 1-in 1-out, 2-in 1-out, and 1-in 2-out transactions. If we want to make large # outputs cheaper we can adjust the second constant.