A familiar problem for our family, too. We like to rent apartments. Do a site search and you will find lots of comments and ideas. In Madrid, we have stayed at the one owned by Rosa and Alberto on Huertas and at Apartasol. A recent post spoke of another that looked good. In Sevilla, check out www.alojamientos-sevilla.com
We loved staying with them. Another site is www.sevilla5.com
However, I have not used them. It has taken a lot of looking, but we have not yet had to rent 2 rooms. If your children are young, you can get away with putting them both in a single extra bed.