Is it natural to say, for example 散歩しに行く? Or would you rather say 散歩に行く? If both are acceptable, is there any difference in meaning or usage?
散歩に行く is used quite a bit more frequently. Looking around, most people don't really see a difference between the two and consider both correct.
It's like saying in English, 'I'm going for a walk.' versus 'I'm gonna go for a walk.'.
Many if not most other cases of V + に行く would likely be more appropriate with the し.
For example, if you were talking about tennis and you just said テニスに行く, one wouldn't understand if you were going to watch tennis or going to play tennis (見に行く/しに行く) .