I have made Asian coleslaws multiple times, and they work very well. My main suggestion would be to heat the dressing before adding it to the slaw. Particularly if you're using scallions, the heated dressing wilts it just enough to cut some of the sharpness of the raw veggies. I'd probably make my own dressing from rice vinegar, neutral oil (such as canola) and a touch of sesame oil. Add in spices such as garlic, ginger, etc. You can also vary recipes such as this.
You could also try using unexpected ingredients. I make a salad from cubed jicama, apple, and ripe avocado, topped with lemon juice, olive oil, and a touch of chili powder or cayenne. You get the crisp sweetness and some creaminess from the avocado.
If they're not fans of cucumbers, how do they feel about pickles? Those could also be a nice addition to a coleslaw. Or you could try marinated mushrooms. Either of those would add a vinegary sharpness that would cut nicely through the creaminess of the rice and the satay.
This also brings to mind a preparation I've seen for vegetables in a prepared salad. Blanch your veggies and shock them in an ice bath. Then give them a vinegary dressing and lay them on the plate in attractive ways. This could include green beans, carrots, beets, broccoli, cauliflower, asparagus, potatoes, etc. You could achieve similar effects by serving roasted vegetables. (Either from the grill or oven-roasted.) These are quite good cold or warm.