While I am not able to suggest any particular carrier, I would like to suggest you to tell roughly where in the world you are located. If you live in, say, New Zealand, a really great carrier in Spain might not be that useful to you.
As "straight talk" seems to be, among other things, a US ceullular carrier, I would guess you are located somewhere there. Since I live in Europe, my insights into the US telecom market is negligible, though I am under the impression that the quality of service might differ significantly between locations, so, while it might be wise not to divulge exacly where you live, I think something like "rural norhwestern Virginia" or "downtown metropolitan Texas" might be helpful to those in the know.
There is a Cosmo Linux subforum here on OESF. That might be a better place to post questions like these, as more of the Linux users might see them there. Though my Linux knowledge is very limited, I think (but beware, I might be completely wrong) your choice of Linux distro might matter more than your choice of wireless carrier. Especially non-VoIP telephony support seems to be lacking in many distros.
I know there is a version of Sailfish for the Cosmo, that even has a subforum of its own here os OESF. I think they've have at least some telephony support. Also, in "the Update #65 from Cosmo Communicator" email newsletter from Planet Computers, they've linked to a video on Vimeo
https://player.vimeo.com/video/472188188where they talk about Cosmo telephony in Linux. I don't know which distro they are using, and it seems to not quite be ready for launch yet, but, if interested, that video might be able to give you some useful clues. Good luck.