This could really be all over the place as not one sock fits all and everyone's needs/goals are different. Many online sites have lists available, I like what's on Balanced Bites via @Violets post. Personally I dig yuca, plantains, banana, tubers, sweet potatoes, parsnips, squash, taro..

I'm super lucky that where I live in Brooklyn I have full access to yuca/plantains/taro 1 block away from my apartment. Win!

If anyone wants to try plantains: I find that slashing the skin with a knife then dropping into boiling water for a few seconds allows the skin to come right off. When green they're a pain to deal with.

Yuca: Cut into 2" to 3" long pieces. On the freshly cut end you will see the "ring" of bark that needs to be removed, it is about 1/16' thick, I use a knife or peeler. Once the bark is removed use your knife to score an "X" on each cut end of the yuca pieces - this helps them split later on. Drop them into boiling water and boil until they are soft and can be pierced with a fork or knife - 20 to 30 minutes. They may also be splitting open at this point. The yuca can be served mojo sauce made with whatever fat/oil you like + lime juice or sour orange juice, and fresh garlic spooned over the top. For fries you put in the fridge to cool. Once it is cooled, and the yuca is firmed up a bit, cut the pieces in halves or quarters, it will naturally let you know what it wants, and remove the fibrous strip out of the very center. Squeeze the quarters or halves lightly in your hands to compact them. Drop them in fat/oil to deep fry or you can pan fry in less fat/oil, turning a couple of time until browned or golden, you can also roast in the oven. You will find that how long you boil them (and how hard you squeeze them) for will vary the consistency of the final product considerably, from denser (less time boiling) to looser (more time).

Taro is awesome and, to me, pretty flexible like the plantain, so many things to do with it. An easy one is put bite sized pieces into a pot with 1c stock, 1tb maple syrup. Bring to a boil and cook down until the liquid is almost gone. Add 1tb coconut aminos. Thin out with 2tb white miso and a little water until more liquid rather than paste-like, add to the pot. Let simmer and y_u_m.

Good times!

i love me some yuca!

oops, wrong spot. Can this be deleted?

You might want to look at this previous question covering starches:

http://paleohacks.com/questions/31667/what-are-some-nutritious-starch-options#axzz1rpJ5qN6u

It was about getting nutritious starches into your diet. Hopefully that helps.

Safe carbs depends on who you listen to. Robb Wolf will tell you tequilla is the only safe carb. Mark Sisson would add a tiny amount of milk. Read Sally Fallon's 'Nurishing Traditions' for a pretty comprehensive list of Weston A. Price go-to foods. But in her excellent book she warns not all carbs are for everyone. Some can handle lactose and sourdough wheat (like me - go ahead and ban me mods ;) ), most agree on yams. Personally I love veggies and yams with a little sourdough bread (drenched in butter or soaking up deep orange yokes), lots of raw local honey, and raw local goat milk. I like beans once in awhile if they're soaked two days and cooked the same, swimming in pastured lard. White rice won't bother if you're insulin sensitive. Ditto Irish potatoes. If you're on the fence, go large with the pseudo-potatoes like beets, rutabagas, carrots etc. OK, now I'm hungry. . .

Here's a great list done by Diane Sanfilippo of Balanced Bites: http://balancedbites.com/2011/08/paleo-diet-carbs.html I don't know the prices per calorie but I imagine it would vary widely depending on season and locale.

I love bananas. They only work out to around 2.7 calories per penny, but they're still dirt cheap. They're by far my favorite post-workout food.

Taro root is probably my favorite safe (errr, safe only when cooked) starch, but the cheapest I can find is probably around 1 calorie per 1 penny. It's a bit expensive for me, but I love it. I have no idea what people think of taro, since I rarely hear it mentioned.