Pork Rinds!!! Love eating them with guacamole. You can get good ones (chicharones) from Latin markets, or cheap ones in a regular grocery store near the snack food.

If you're set against corn, you could do worse than zucchini chips, kale chips or pork rind chips, all suggested in this hack. I'd go for the pork rind, personally.

However, prepared (nixmalated) corn, fried in lard or coconut oil is probably not the worst non-paleo food you'll eat. This is contentious though.
See these hacks for pros and cons:

• http://paleohacks.com/questions/14356/issue-with-corn#axzz1EDurEjGv
• http://paleohacks.com/questions/19543/real-impact-of-popcorn-as-only-non-paleo-food#axzz1EDurEjGv
• http://paleohacks.com/questions/16932/tortillas-how-evil-are-they#axzz1EDurEjGv

I actually use cucumber slices as "chips" to scoop up my guac and salsa! Plus because they are pretty mild... it doesn't mess up the flavor of my much loved salsa and guac AND they are lite allowing me to eat TONS of it!

My two favorites are dried plantain chips or unsweetened banana chips. The flavor in both is pretty mild, and offer that tortilla chip crunch.

I'm currently enjoying unsweetened banana chips I ordered from www.nuttyguys.com because it's difficult to find unsweetened banana chips in stores. Plantain chips are pretty easy to find. I like the Trader Joes brand because they are so cheap, but they are also a little heavy on the salt. Not terrible for a once in a while treat.

I also warn to limit eating either of these to the occasional snack. They are often cooked in sunflower oil (and sometimes canola), which I'm not a fan of, but I'm willing to deal with on occasion for a treat. It's definitely better than the alternative - tortilla chips.

I was a chip addict before dropping them completely. They are my nemesis and I could still sit down and eat an entire bag of them. That being said, every alternative I've tried has just been a let down.

I no longer try to get the satisfying and comforting crunch from other foods that chips bring. It just makes me sad because nothing really compares (woe is me, lol). Instead, I try to enjoy the "vehicle" for what it is and not compare it to the magnificent chip. 8)

I love salsa and other dips as well and have found the best vehicle is, as most others have said, some type of veggie. My favorite is sliced bell peppers. I prefer red or yellow over green, but they're all pretty good.

Fennel bulb makes good chips for guacamole.

Bacon!!!!!!! Bacon is a great transport vehicle for guacamole!

how about romaine...down towards the end where it is a lighter green and the stalk is crunchier....kale chips, carrots, sliced chicken, rolled up in liverworst, rolled in boars head turkey or ham, plopped on top of my salad! stuffed in compari tomatoes.

Enjoy!

Plantain Chips or Pork Rinds.

There are a handful of brands that fry their plantain chips in Palm Oil, and even low-salt varieties (we have a no-salt palm oil plantain chip in Central FL under the brand "Chifles". Maybe not paleo, but they don't upset my GI tract or give me GERD from eating them either, like normal chips fried in NastyFat(tm).

As far as the pork rinds go, I like going to local mercados where they make their own MASSIVE chuccarrones daily. When I say "no sal, por favor" they look at me like I'm from Mars, but it stil gets me my crunch fix. Also, the big plate-sized chuccarrones make a fantastic landing pad for no-beans chili.

I love salsa and guac too. Tortilla chips are a huge weakness of mine too! Here are some alternatives, Fresh red pepper, broccoli, cucumbers, stuff celery with guac, flax seed crackers, all natural pork rinds.

Pre-Paleo, Chips and salsa were my favorite snack. I've been trying different things to substitue, and while I havent found anything perfect, I have discovered that a good slice of hard cheese dipped in salsa is amazing, and hard boiled eggs arent bad either. Strips of Chicken too :)

Food For Life brand (famous for their sprouted ezekiel breads) makes organic sprouted corn tortillas with no added oils.

The ingredients are: Organic Sprouted Whole Kernel Corn, Filtered Water, Sea salt, Lime.

I know corn itself has the omega6 factor, but as long as you don't overindulge, these do make pretty tasty chips. I just cut them up into cips, sprinkle some sea salt, and bake them for about 8 minutes in the toaster oven.

Totally healthy? nah. probably not. But not exactly aweful either.

Warmed up these do make for excellent tacos. At least you know they are nixtamalized and you're not getting oils and weird ingredients.

Sweet potato chips aren't bad if you can find a good brand. Or if you want to take an afternoon to make them, they're not too hard--just slice a sweet potato with a vegetable peeler, and bake in the oven, or fry in olive oil on a stove top. Season w/ salt and pepper when done.

You can also make a pretty good tortilla chip out of almond meal and eggs, rolled super thin and baked in the oven.

We've found that carrots go really well with guac. We've also used dehydrated yam slices, which turned out really well.

Two things I've tried: almond meal crackers (pretty good) and shredded cheese...uh thingies. Essentially you mix grated cheddar (or whatever) and parmesan, press them into balls and bake on parchment until flat and brownish around edges. They melt down into chip shapes and are pretty sturdy when cooled.

I like to slice steak pretty thin and dip the pieces in guac and salsa. Delicious!

Jicama, and what everyone else said.

endive is a great scooper for all dips. Also find the plantain chips work for me (in palm oil). I get the small bags so I won't overdo it.

Jicama is a nice crunchy alternative.

I like to slice yams very thin (a mandolin or a food processor with a slicing blade is kind of necessary) coat them in a bit of bacon fat or coconut oil and dehydrate them overnight.

I also recent found potato chips fried in olive and in avocado oil at the whole foods near me. But at $5 per bag I still haven't tried them.

Finally, I have been meaning to try frying up some fresh corn tortillas (treated with lime) in some coconut oil. Not paleo I know... But I think that the stress of worrying if something is "paleo" or not is worse than just enjoying the food.

Pea pods, large carrot "coins" and radishes are great for dips.

Make your own flax crackers with flax seeds and tamari. Soak 2 cups flax seeds in 2 cups water for 2 hours until it's gooey. Stir in 1/4 cup tamari and add salt/herbs or other ingredients to your liking. Spread the mixture onto a pan and bake in an oven for about 30 minutes or until suitably dry. Or use a dehydrator if you like them raw.

Here's another recipe: http://www.neverhomemaker.com/2010/02/homemade-flax-crackers.html

You might find raw flaxseed crackers in health stores or vegan eateries. I like these: http://www.freshthegoodfoodmarket.ie/wp-content/gallery/natashas-living-food/sprouted-flax-crackers.jpg

If you want something less heavy, try kale chips.

Maybe Bacon!

Or Parmesan crisps

Crispy Bacon!!!!!!

There is no reason to stop eating tortilla chips, just make healthy tortilla chips yourself: paleo tortilla chips.

I haven't tried this yet, but over at EverydayPaleo.com, plantain chips were a recommended substitute. Sounds yummy to me!

I brown some grassfed ground beef with a little Garlic Basil and Fennel and then Generously Heap my Homemade Pico De Gallo on top... Then I can eat it with a Spoon... MMM.

If you have the time and would want to make the effort - here are two nice GTV's (guac transport vehicles).

http://www.elanaspantry.com/betsys-multi-grain-crackers/

http://www.lifeasaplate.com/2011/02/14/pepita-parmesan-crackers-with-warm-scallion-dip/

pork rinds, carrots, cauliflower heads all work well.