Se habla español? If you're fluent in the language I'd recommend Cartagena, Colombia. I've been there twice and actually got married there last year (no, it wasn't a particularly inexpensive wedding, but it had to be in Colombia so we went big). If you stay in the old city (San Diego) or in Getsemani it will be pretty safe. There's no real street crime in those areas other than pickpockets, so just be mindful of your wallet and documents. It's a little bit more touristy there than in other parts of Colombia, but it's such a beautiful city with so much history that you shouldn't even notice. And the food is spectacular there. I haven't been to Panama or Nicaragua, but what I've heard from folks who are traveling down through CA to SA is that the food significantly improves when you go from Panama into Colombia.
Prices aren't particularly cheap in Colombia, but the Peso dropped significantly last year when oil crashed, so it won't be too bad.