See the 'EDIT' for solution
EDIT: If in Personalize Display you use the gray drop-down box and select 'Icon', but make its TEXT a huge size like '13', you get something approximating 'medium' for ALL the icons in taskbar and desktop toolbar. I just did that, mimicking the setting I have in one of my Win7 machine themes. It worked well. Presumably if that size is too small for your taste, then increase the font size from '13' to something higher. Effect is immediate.
Don't forget to save the theme. Original post, now kinda obsolete, follows below the === marks.
==========
Yeah, they are always too big or too small no matter what you do. There are TWO settings, though. For desktop icons, you have to right click while in that toolbar and when you see 'View', hover on it and a flyout will give you the option of 'large' icons or 'small', not medium. So small is soooo small that you must put your nose in the screen to see them, and large is soooo large that it's intrusive even from three feet away.
So I tried all the bit about sizing the text, the individual sizings in 8.0 and 8.1 with individual things like the Title versus Icon, etc. All are disatisfactory. But there's one more option to try: using the old Win95/98/XP/Vista 'Plus!' themes which used to be in Program Files. If I put an old theme with the right sizes and colors in the Themes folder, and then click on THEMES.exe -- the whole Plus! folder has to be in Win8's own Program Files directory for this to work -- if I then click on THEMES.exe, it gives me my list of themes, and then I make sure to only tick the fonts and colors (lest it override the actual Win8 theme entirely). Then it works. Win8.1 later updates might reset the fonts, but I put Themes.exe in my taskbar so can click it quickly.
So now the question is, will it also resize the icons. Not sure. Will test. If I don't report success later on, I didn't have success (at least not yet).
One good thing to come out of this, is proof how much better the XP interface really was. If only they retained the OPTION of keeping it and just made changes under the hood, or didn't make MANDATORY their new horrible GUIs (and bad search, Vista forward). Makes you realize how productive, you once were.