MilesRus,
A search of the Taca site indicates in addition to the direct flight to Costa Rica from Dallas you mantioned there is also a direct flight to San Salvador from Dallas as well. From Houston a direct flight can be made to Belize on Taca each day, connections to other cities in Central America can be made from both of these transfer points without an overnight stay. Costa Rica is not your only option!
You will have to get passports for your kids if you take them to any of these destinations but if you get a flight on KLM to Europe you will also need passports. Passports for the kids are less expensive but only good for five years. By the way Aeropostal and Avianca are still partners in GP so you may be able to get to Europe using LP carriers because the partners both still have service to Spain.
Just as a side note after having been to Cancun, I would never go back especially with children. My thoughts on Cancun: Shuttle service from airport to Hotel maybe 10 miles away $80.00 (total rip-off) Stayed at JW Marriott (Award stay) nice hotel, very ritzy and all options pricey. Sixty-five dollars for breakfast one morning for the four of us, not exactly family friendly. Restaurants throughout Cancun very expensive; (by now you can tell I am a little cheap) Beach is lined with high-rise hotels and is reminiscent of Miami. The McDonalds on Cancun had prices exceeding those in Paris. The ocean (a beautiful aqua blue) was so rough my kids could not swim in it the week we were there.
About one hundred miles south of Cancun you could go to Belize. Swim with the Sharks and Rays for about eight bucks in a protected coral reef. Buy breakfast for the family for about ten dollars total. Cheap Lobster and seafood dinners; they speak English unlike Cancun and seem to like Americans. Belize was part of the former British Empire until about ten years ago. I have been to Cancun, Costa Rica and Belize, and the only place I would never consider visiting again is Cancun, don’t waste your time and a lot of your money trying to get there.
I found this map of Taca routes it might be helpful in making plans. Kind of difficult to tell all destinations, looks like the heartland of America is without any service:
http://www.taca.com/images/lyf/lyf-routemap-eng.gif