Small red potatoes would taste great but because of the size you will end up with more skin in your mash. Regular sized potatoes are preferable.