Unfortunately, this does not help me much. This is my first tx. To a certain degree I blame my Bitcoin client for this. (It should know my kb and tell me ACCURATELY how much the fee should be before I send (right?).
Correct. A well designed and well written wallet should properly calculate the generally accepted minimum fee.
How am I supposed to know the kb? My client (Electrum), actually suggested: .001 - WAY OVER.
I thought Electrum lets you set a minimum fee per kilobyte in the settings? What is your setting? If you set it to 0.0002 BTC, then it accurately calculated (5 kB * 0.0002 BTC = 0.001 BTC). Regardless, arbitrarily choosing a fee that is different than your wallet is suggesting without understanding the repercussions of that decision results in certain consequences.
They say hindsight is 20/20, however the question still remains: What do I do now?
Wait for a miner (or mining pool) to be generous enough to confirm your transaction. There's a pretty good chance that it will be confirmed within the next 3 to 10 days.
Alternatively, you can try asking in the Electrum sub-forum if there is a way to remove a transaction from the Electrum wallet. If so, then you could shut down the Electrum wallet, remove the transaction from the wallet, and wait a few days. Eventually (usually within 2 to 4 days) if the transaction isn't confirmed, it will be dropped from the memory pool of the peers. Then you could start the Electrum wallet back up and the bitcoins should be back in the wallet.