I agree, four people in a room in Europe is very unusual. I would allow for the possibility of having to go for two rooms. Rooms with two beds large enough to sleep tow adults and two children will not be easy to find. I understand your problem, but looking at your itinerary, I would imagine that to get that size of room you could try La Perouse at Nice, they certainly would manage that. I would not hold much hope for anything "budget" in these locations. Sorry to sound negative!