I went from 4 to 5 to 7 strings. I originally went to the 5-string because I was primarily playing gospel and wanted the low Eb, Db etc. Then, I started hearing Bbs below my B. People started to tune their basses Bb-Gb. I didn't want to do that. So, I went to the 7-string now tuned B-F. But, Since i finally got new strings and a new nut, I'll have it setup and tuned F#-C. THat way I can get those Bbs, Abs etc.
As far as recommending staring with a 4 or 5 string. I don't think it makes much of a difference. But I think the 5 string would be better for gospel.