nightowl, on an 802.11b wireless connection, real-world throughput is like 2-5Mb/s. For ESP 3DES/HMAC-SHA1, the per-packet byte overhead is not going to be the bottleneck - the crypto speed of the endpoints is. 2Mb/s isn't too much for a PC, but 5Mb/s is starting to get to be a pretty interesting level of performance. Most SOHO VPN routers without crypto accelerator chips can do maybe hundreds of kb/s. SOHO VPN routers with crypto accelerator chips can do a few Mb/s. More than that and you're talking big $$.
ScottMac, I'm a bit confused by your fragmentation statement - it really just doesn't parse. Encryption has nothing at all to do with it, only VPN technology. For IPsec, there are well defined rules for when the inside DF bit gets copied to the outside DF bit and for IPsec security gateways to proxy ICMP too bigs in certain ways to make PMTU discovery work right. That doesn't mean the vendors get it right; IPsec gateway vendors are amazingly underclued for the amount of trust that's placed in their products. For other VPN technologies, I don't know what they do... I assume that most of them ignore DF entirely on the inside and don't set DF on the outside, and thusly create outer fragmentation.
In the case of 802.11 wireless, you can cheat a little - 802.11 if I'm not mistaken supports frame sizes up to somewhere in the neighborhood of 11kb. If your endpoints support it, you could construct a MTU=1500 virtual interface and up the 802.11 physical interface MTU to 2048 or whatever, and work that way. This would be very handy if you're doing the VPN just for over the air and then routing to another Ethernet network, as you can achieve an end-to-end MTU of 1500. (for various reasons, your life will be simpler if your MTU to most of the world is 1500. Not supposed to matter, but it sometimes does).