Interesting coincidence - I bumped into a game design article earlier today about balancing luck and skill in games. http://gamedevelopment.tutsplus.com/articles/when-i-win-its-...
The article discusses how different players prefer different ratios of luck vs skill, so making the most "fun" game in this regard really depends on who your target audience is. Similar to your thoughts on randomness. :)