If CPU usage to verify a transaction is NOT related to the transaction size, then you open yourself up to denial-of-service attacks. Like:
Create an Ethereum transaction with a (huge!) fee that will pay for 60 seconds of CPU execution time.
... but craft it so execution takes 61 seconds (or, heck, make it an infinite loop, maybe you'll tickle a bug in the execution termination code).
Now broadcast it. It will be rejected for insufficient fee, but only after peers have wasted 60 seconds of CPU time. And if the transaction is rejected, the attacker won't pay the fee.
Sorry if this has been addressed before:
In Ethereum (or in Bitcoin with Turing-complete scripts), could this idea be used by a miner to delay competing miners, rather than sabotage the network with a DDOS-type attack?
Namely, the malicious miner creates a transaction with a script that takes a long time to complete, and a fee that forces it to be included in the next block; and computes the script's outcome before issuing it. Would that give him an edge over other miners?