I personally prefer pasta salad over coleslaw, but considering the fact that you are serving several other starches, I would go with coleslaw.
How about Caesar Salad or Garden salad? They are what I usually serve with the type of menu you noted above, but I know coleslaw is a favorite of many (just not me).