A spicy vegetable which stays in a sandwich?
My home pickled beans get spicy because there's a dried red pepper or two in the jar, along with a dill head and some garlic cloves. The beans are very nice in a sandwich. But you could pickle-and-spice anything at all and use it to jazz up the sandwich. The texture is that of a soft vegetable.

Also, look into mustard greens and their relatives. They look like lettuce or kale, but taste distinctly spicy. The texture is more lettuce-y than cucumber or slices of pepper, but it wouldn't be out of place on a sandwich.