I think that I have a solution: We have that $min \{f(a,b): a,b\in\mathbb{N}$ and $0<a<b<1000\}=668$ and $max \{f(a,b): a,b\in\mathbb{N}$ and $0<a<b<1000\}=1334$. I'll do the minimum first. We show that for each $S$ that is a maximal "skipping set," there are more than $\frac{1}{3}$ of the elements of $\{1,2,\dots ,2003\}$ in it. Fix any $a<b.$ Then consider the following template of the first $3b$ (or if necessary, $2003$) integers: in the first $b$ integers, include the union of the sets $\{1,2,\dots ,a\}$, $\{2a+1,2a+2,\dots ,3a\},\dots ,\{ma+1,\dots ,b\}$ where $m$ is the greatest even integer such that $ma<b$. Now, for the second group of $b$ integers, include all of the elements that were not included in the first $b$ integers $mod$ $b$. And finally, do not include any of the third $b$ integers. Then we have precisely $\frac{1}{3}$ of elements in $S$, and $S$ is indeed a skipping set. Since the first $a$ integers are included in $S$, when we repeat the structure of $S$ $mod$ $3b$ for all integers less than $2003$, we will have more than one-third of the elements. Here's a quick example for $a=2$ and $b=7$: $\{1,2,5,6,10,11,14\}$ and then just repeat its structure $mod$ $3b$ (I hope that's clear). Now, since (I hope it's kinda obvious) $f(1,2)=\frac{2002-1}{3}+1=668$, we are done with the minimum. For the maximum, consider the partition of the first $2003$ integers like so: $A_{1}=\{1,b+1,2b+1,\dots ,(n-1)b+1\}$ ... $A_{b}=\{b,2b,3b,\dots ,(n-1)b\}$ where $n$ is the greatest integer such that $(n-1)b<2003$. Then by the pigeonhole principle, we can have just $\lfloor\frac{n+1}{2}\rfloor$ elements from each set in $S$. This means that for $z\in\mathbb{N}$ there can be at most $\frac{z+1}{2z+1}\cdot 2003$ elements in $S$. This is maximal for smallest $z$, and thus there should be at most $\lfloor\frac{2\times 2003}{3}\rfloor=1335$. But for each of these $S$, at least one of the elements must be removed since for any $a<b$, there will be two elements with difference $a$. So then we have $f(a,b)\le 1334$. And finally, $f(667,668)=1334$ since $\{1,2,\dots ,666,667,1336,1337,1338,\dots ,2002\}$ suffices.