You can buy a new phone from Verizon or one of its distributors, or a used phone that has been unlocked. Unlocked phones can be programmed to work on different networks, but not all phones can work on all networks. I went through the same thing as you about a month ago, wanted a new phone but stayed with Verizon. I found out that places like amazon and letstalk.com don't deal with existing customers. I also found that brand new phones are ridiculously expensive if you don't sign a contract, and used phones really aren't much cheaper. After going around and around, I ended up buying my phone at Radio Shack and only signing a 1 year contract. If I had bought the same phone and plan at Verizon, it would have cost me $100 more.
If you are ok with signing a 2 year contract, there's many phones you can get for free. If you don't want to sign a 2 year, you'll have to do some more digging to find a deal. And if you don't want to sign any contract, you're outta luck, stuck paying almost full price for a phone ($200-300).