We search for new charmless decays of neutral $b$--hadrons to pairs of charged hadrons with the upgraded Collider Detector at the Fermilab Tevatron. Using a data sample corresponding to 1 fb$^{-1}$ of integrated luminosity, we report the first observation of the BsKpi decay, with a significance of $8.2sigma$, and measure $BR(BsKpi) = (5.0 pm 0.7stat pm 0.8syst)times 10^{-6}$. We also report the first observation of charmless $b$--baryon decays in the channels Lbppi and LbpK with significances of $6.0sigma$ and $11.5sigma$ respectively, and we measure $BR(Lbppi) = (3.5 pm 0.6stat pm 0.9syst)times 10^{-6}$ and $BR(LbpK) = (5.6 pm 0.8stat pm 1.5syst)times 10^{-6}$. No evidence is found for the decays BdKK and Bspipi, and we set an improved upper limit $BR(Bspipi) < 1.2times 10^{-6}$ at the 90% confidence level. All quoted branching fractions are measured using $BR(BdKpi)$ as a reference.