We study a model of $N$ fermions in a quantum dot, coupled to $M$ bosons by a disorder-induced complex Yukawa coupling (Yukawa-SYK model), in order to explore the interplay between non-Fermi liquid and superconductivity in a strongly coupled, (quantum-)critical environment. We analyze the phase diagram of the model for an arbitrary complex interaction and arbitrary ratio of $N/M$, with special focus on the two regimes of non-Fermi-liquid behavior: an SYK-like behavior with a power-law frequency dependence of the fermionic self-energy and an impurity-like behavior with frequency independent self-energy. We show that the crossover between the two. can be reached by varying either the strength of the fermion-boson coupling or the ratio $M/N$. We next argue that in both regimes the system is unstable to superconductivity if the strength of time-reversal-symmetry-breaking disorder is below a certain threshold. We show how the corresponding onset temperatures vary between the two regimes. We argue that the superconducting state is highly unconventional with an infinite set of minima of the condensation energy at $T=0$, corresponding to topologically different gap functions. We discuss in detail similarities and differences between this model and the model of dispersion-full fermions tuned to a metallic quantum-critical point, with an effective singular dynamical interaction $V(Omega) propto 1/|Omega|^gamma$ (the $gamma-$model).