The rubber feet on Apple's newer keyboards are teeny, tiny, little hard bumps, and they don't prevent the keyboard from sliding around on some types of surfaces at all (like they should). Judging from the dirt on mine they look like in addition to being very hard plastic they also only have a contact area of one square millimeter.
I think the easiest, least destructive, and cheapest way would be to buy new soft rubber feet. The main point would be to make sure they are soft, not hard. Also, the larger the rubber feet, the more force they will be able to resist when being pushed around.
I found two products on Amazon that could do the job just fine. If you don't mind the shape of these rubber feet, they are a good solution:
but if you prefer to have a larger contact area, these would be a great choice: