Why would it be difficult in their eyes to serve Hashem?
Malbim: Some things conduct according to nature and the Ma'arachah (arrangement of the stars), and they think that serving others will help for these things.
Why is Yehoshua telling them to choose?
Malbim: You cannot serve Hashem and something else.
Why did he mention these two idolatries?
Malbim: Perhaps you think that the Ma'arachah will conduct with you based on your origin, or based on where you live now (so one of those idolatries will help).