Finding largest closest subsets
Let us consider your "base problem" and the special case of $p = 1/2$.

Assume that we are given a graph $G = (V,E)$ and a positive integer $k \le |V|$.

Construct an instance of your problem as follows:


Our "alphabet" is $A = V \cup \{ 0,1,\dotsc,k-1 \}$.
The sets $s_i$ are indexed with $i \in I = E \cup \{ \bot \}$.
For each $e = \{u,v\} \in E$ we have $s_e = \{ 1,2,\dotsc,k-1, u, v\}$.
We also define $s_\bot = \{ 0,1,\dotsc,k-1 \}$.


Observations:


There is a trivial solution $s$ of size $2k-2$: just take a subset $s \subseteq A$ with $\{1,2,\dotsc,k-1\} \in s$ and $|s| = 2k-2$. Clearly $|s \cap s_i| \ge k-1$ for all $i$.
There cannot be a solution of size $2k+1$ or larger: it would imply $|s \cap s_\bot| &gt; k = |s_\bot|$, a contradiction.
If there is a solution $s$ of size $2k-1$, we can pad it with an arbitrary element to obtain a solution of size $2k$.


Hence the key question is whether there exists a solution $s$ of size $2k$.


Assume that we have a solution $s$ of size $2k$. Then $s_\bot = \{0,1,\dotsc,k-1\} \subseteq s$. Hence $s = \{0,1,\dotsc,k-1\} \cup X$, where $X \subseteq V$ and $|X| = k$. Moreover, if $e = \{u,v\} \in E$, we must have $|s \cap s_e| \ge k$, which implies $e \cap X \ne \emptyset$. That is, $X$ is a vertex cover of size $k$.
Conversely, if we have a vertex cover of size $k$, we can construct a solution of size $2k$.


Hence it is NP-hard to find an optimal $s$. The same idea can be used to show that the problem is hard for any $0 &lt; p &lt; 1$.



Edit: Now a natural question is whether there is an approximation algorithm – for example, can one always find a feasible solution $s$ that is within a constant factor of the largest feasible solution.

However, this does not seem to be the case. It seems that it is actually NP-hard to find any non-trivial solution (i.e., a solution $s \ne \emptyset$), at least for certain values of $p$. The construction is a bit messy, though, but I can try to work out the details if needed.

Anyhow, it seems that to get anything positive (with provable performance guarantees), you need to relax your constraints a bit.